Бинарный поиск
Другим относительно простым методом доступа к элементу является метод бинарного (дихотомического, двоичного) поиска, который выполняется в заведомо упорядоченной последовательности элементов. Записи в таблицу заносятся в лексикографическом (символьные ключи) или численно (числовые ключи) возрастающем порядке. Для достижения упорядоченности может быть использован какой-либо из методов сортировки (см. 3.9).
В рассматриваемом методе поиск отдельной записи с определенным значением ключа напоминает поиск фамилии в телефонном справочнике. Сначала приближенно определяется запись в середине таблицы и анализируется значение ее ключа. Если оно слишком велико, то анализируется значение ключа, соответствующего записи в середине первой половины таблицы, и указанная процедура повторяется в этой половине до тех пор, пока не будет найдена требуемая запись. Если значение ключа слишком мало, испытывается ключ, соответствующий записи в середине второй половины таблицы, и процедура повторяется в этой половине. Этот процесс продолжается до тех пор, пока не будет найден требуемый ключ или не станет пустым интервал, в котором осуществляется поиск.
Для того, чтобы найти нужную запись в таблице, в худшем случае требуется log2(N) сравнений. Это значительно лучше, чем при последовательном поиске.
Программная иллюстрация бинарного поиска в упорядоченном массиве приведена в следующем примере, где a - исходный массив, key - ключ, который ищется; функция возвращает индекс найденного элемента или EMPTY - если элементт отсутствует в массиве.
{===== Программный пример 3.5 =====} Function BinSearch(a : SEQ; key : integer) : integer; Var b, e, i : integer; begin b:=1; e:=N; { начальные значения границ } while b
Трассировка бинарного поиска ключа 275 в исходной последовательности:
75, 151, 203, 275, 318, 489, 524, 519, 647, 777
представлена в таблице 3.4.
| Интерация | b | e | i | K[i] |
| 1 | 1 | 10 | 5 | 318 |
| 2 | 1 | 4 | 2 | 151 |
| 3 | 3 | 4 | 3 | 203 |
| 4 | 4 | 4 | 4 | 275 |
Таблица 3.4
Алгоритм бинарного поиска можно представить и несколько иначе, используя рекурсивное описание.
В этом случае граничные индексы интервала b и e являются параметрами алгоритма.
Рекурсивная процедура бинарного поиска представлена в программном примере 3.6. Для выполнения поиска необходимо при вызове процедуры задать значения ее формальных параметров b и е - 1 и N соответственно, где b, e - граничные индексы области поиска.
{===== Программный пример 3.6 =====} Function BinSearch( a: SEQ; key, b, e : integer) : integer; Var i : integer; begin if b > e then BinSearch:=EMPTY { проверка ширины интервала } else begin i:=(b+e) div 2; { середина интервала } if a[i]=key then BinSearch:=i {ключ найден, возврат индекса} else if a[i] < key then { поиск в правом подинтервале } BinSearch:=BinSearch(a,key,i+1,e) else { поиск в левом подинтервале } BinSearch:=BinSearch(a,key,b,i-1); end; end;
Известно несколько модификаций алгоритма бинарного поиска, выполняемых на деревьях, которые будут рассмотрены в главе 5.
