Бинарный поиск

Пожалуй, первым приходит в голову следующий очевидный метод: сначала сравнить K со средним ключом в таблице. Результат сравнения позволит определить, в какой половине файла продолжить поиск, применяя к нему ту же процедуру, и т.д. После не более чем примерно log₂ N сравнений либо ключ будет найден, либо будет установлено его отсутствие. Такая процедура иногда называется «логарифмическим поиском» или «методом деления пополам», но наиболее употребительный термин - бинарный поиск.

Недостатком бинарного поиска является необходимость последовательного сохранения списка, что осложняет выполнение операции добавления и удаления элемента.

Основная идея бинарного поиска довольно проста, детали же нетривиальны, и для многих хороших программистов не одна попытка написать правильную программу закончилась неудачей. Одна из наиболее популярных реализаций метода использует два указателя - l и u, соответствующие верхней и нижней границам поиска, и состоит в следующем.

Алгоритм B. (Бинарный поиск). С помощью данного алгоритма разыскивается аргумент K в таблице значений R1, R2,..., Rn, ключи которых расположены в возрастающем порядке: K1< K2<...< Kn.

B1. [Начальная установка]. Установить l < =1, u< =1.

B2. [Нахождение середины]. (В этот момент мы знаем, что если K есть в таблице, то выполняются неравенства Kl £ K £ Ku.) Если u< l, то алгоритм заканчивается неудачно; в противном случае установить i £ (l-u)/2: теперь i указывает примерно в середину рассматриваемой таблицы.

B3. [Сравнение]. Если K< Ki, то перейти на B4; если K> Ki, то перейти на B5; если K=Ki, алгоритм заканчивается удачно.

B4. [Корректировка u]. Установить u< =i-1и вернуться к шагу B2.

B5. [Корректировка l]. Установить l< =i+1и вернуться к шагу B2.

Одна важная модификация. Соблазнительно вместо трёх указателей l, u, i использовать лишь два: текущее положение i и величину его изменения E; после каждого сравнения, не давшего равенство, мы могли бы установить i< =i+(-)E и E< =E/2(приблизительно). Этот путь реализуем, но он требует особой аккуратности в деталях, как в приведённом ниже алгоритме; более простые подходы обречены на неудачу!

Алгоритм U. (Бинарный поиск). С помощью данного алгоритма разыскивается аргумент K в таблице значений R1, R2,..., Rn, ключи которых расположены в возрастающем порядке: K1< K2<...< Kn.

U1. [Начальная установка]. Установить i < =N/2, m< =N/2.

U2. [Сравнение]. Если K< Ki, то перейти на U3; если K> Ki, то перейти на U4; если K = Ki, алгоритм заканчивается удачно.

U3. [Уменьшение i]. (Мы определили положение интервала, где нужно продолжать поиск. Он содержит m или m-1 записей; i указывает на первый элемент справа от интервала.) Если m=0, то алгоритм оканчивается неудачно. В противном случае установить i< = i-(m/2); m< =m/2 и вернуться на U2.

U4. [Уменьшение i ]. (Ситуация та же, что и в шагеU3, только i указывает на первый элемент слева от интервала.) Если m=0, то алгоритм оканчивается неудачно. В противном случае установить i< = i+(m/2); m< =m/2 и вернуться на U2.