Re: Поиск в упорядоченном массиве

From

Oleg Shatalov ()

To

Sergey Khudyakov

Date

2002-09-24T17:05:23Z

Area

RU.ALGORITHMS

From: Oleg Shatalov <oleg@lakes-environmental.com>


Привет, Сергей!

>  Есть массив числовых данных упоpядоченный по возpастанию [a1,a2,..,an]. И есть
> число b - pезультат измеpения. Как постpоить алгоpитм, чтобы с минимальными
> затpатами вpемени найти в массиве число, ближайшее слева к измеpенному значению?

Двоичный поиск спасет тебя.

Суть его в том, что весь массив делится на каждом шаге на два интервала и берется в
рассмотрение тот интервал, который содержит искомое число.

Более подробно можно посмотреть тут:
http://algolist.manual.ru/search/bin_search.php

Пока,
Олег.
--- ifmail v.2.15dev5
 * Origin: Golden Triangle On Line Inc. (2:5020/400)