Бинарный (двоичный, дихотомический, половинного деления)
поиск относится к наиболее эффективным методам поиска в упорядо-
ченной последовательности
Вначале А сравнивается с ключом средней записи. Результат сравнения позволит определить, в какой половине последовательности
продолжить поиск, применив к ней ту же процедуру и т.д.
После определенного числа сравнений либо ключ будет найден,
либо будет установлено его отсутствие. Структурограмма алгоритма
бинарного поиска представлена на рис.
ключей: 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;