Бинарный поиск
Методы поиска в упорядоченных наборах данных
В последовательности записей с упорядоченными ключами K1<K2<...<KN поиск осуществляется посредством сравнения ключей. Первоначально интервал поиска Q=1, P=N. Q - левая, а P –правая гранцы интервала поиска. После каждого сравнения аргумента поиска А с ключом Ki поиск продолжается одним из следующих 3 способов:
1. Если A < Ki, то записи Xi, Xi+1,..., Xp исключаются из рас-
смотрения и поиск продолжается среди записей XQ, XQ+1,..., Xi-1, т.е.
интервал поиска сокращается и становится равным Q, P=i-1.
2. Если A = Ki, то поиск заканчивается удачно.
3. Если A > Ki, то записи XQ, XQ+1,..., Xi исключаются из рас-
смотрения и поиск производится среди записей Xi+1, Xi+2,..., Xp, т.е.
интервал поиска становится равным Q=i+1, P.
Известны следующие методы поиска: бинарный, однородный бинар-
ный, золотого сечения, интерполяционный, Фибоначчиев поиск, блоч-
ный и др., различающиеся способами выбора ключа Ki для его сравне-
ния с аргументом поиска А. При этом всегда предполагается, что
если А имеется в последовательности ключей, то K1 <= A <= KN.
Введем обозначения
|_ X_| - наибольшее целое, меньшее или равное X (целая часть).
| X | - наименьшее целое, большее или равное Х.
Бинарный (двоичный, дихотомический, половинного деления)
поиск относится к наиболее эффективным методам поиска в упорядо-
ченной последовательности
Вначале А сравнивается с ключом средней записи. Результат сравнения позволит определить, в какой половине последовательности
продолжить поиск, применив к ней ту же процедуру и т.д.
После определенного числа сравнений либо ключ будет найден,
либо будет установлено его отсутствие. Структурограмма алгоритма
бинарного поиска представлена на рис.
ключей: 20 25 29 32 37 38 39 51 53 57 61 99.
Q=1,P=12,i=6,Ki=38: *[20 25 29 32 37
Q=7,P=12,i=9,Ki=53: 20 25 29 32 37 38[39 51
Q=7,P=8,i=7,Ki=39: 20 25 29 32 37 38[ 39 51]53 57 61 99.
Q=8,P=8,i=8,Ki=51: 20 25 29 32 37 38 39[
*[ - означает нижнюю границу интервала поиска, соответствующую
указателю Q.
**] - означает верхнюю границу интервала поиска, соответствующую
указателю P.
Поиск заканчивается удачно, ключ 51 имеет элемент с номером 8.
Пример программы 1.
Пример программы 2
function SearchBin (Arr : array of Integer; A, N : Integer) : Integer;var Up, Down, Mid : Integer; Found : Boolean;begin Up := 0; Down := N; Found := False; Result := -1; repeat Mid := Trunc ((Down - Up) / 2) + Up; if Arr [Mid] = A then Found := True else if A < Arr [Mid] then Down := Mid - 1 else Up := Mid + 1; until (Up > Down) or Found; if Found then Result := Mid;end;