logo
лекции по МОТС / ДИСКРЕТНАЯ МАТЕМАТИКА Графы

9.4.3. Алгоритм бинарного (двоичного) поиска

При использовании упорядоченного массива для представления ассоциативной памяти операция поиска записи по ключу может быть выполнена за время O(log2 n) (где n — количество записей) с помощью следующего алгоритма, из­вестного как алгоритм бинарного (или двоичного) поиска.

Алгоритм 9.2. Бинарный поиск

Вход: упорядоченный массив А : array [l..n] of record k: key;i: info end record; ключ a: key.

Выход: индекс записи с искомым ключом а в массиве А или 0, если записи с таким ключом нет.

b: = 1 { начальный индекс части массива для поиска }

е: = n { конечный индекс части массива для поиска }

while b  e do

с: =(b + е)/2 { индекс проверяемого элемента (округленный до целого) }

if A[c].k > a then

е:=с—1 { продолжаем поиск в первой половине }

else if A[c].k < a then

b: = с + 1 { продолжаем поиск во второй половине }

else

return с { нашли искомый ключ }

end if

end while

return 0 { искомого ключа нет в массиве }

обоснование

Для обоснования этого алгоритма достаточно заметить, что на каждом шаге основного цикла искомый элемент массива (если он есть) находится между (включительно) элементами с индексами b и е. Поскольку диапазон поиска на каждом шаге уменьшается вдвое, общая трудоемкость не превосходит log2 n. 

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4