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

Методы поиска в упорядоченных наборах данных

 

В последовательности записей с упорядоченными ключами 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;