Алгоритмы поиска в упорядоченных массивах

Алгоритм быстрого линейного поиска

Применяя алгоритм быстрого линейного поиска для поиска элемента в упорядоченном массиве, поиск можно прекратить, если очередной элемент массива будет больше искомого. Это будет означать, что искомого элемента в массиве нет. В случае поиска элемента, который есть в массиве, этот алгоритм аналогичен алгоритму быстрого линейного поиска в неупорядоченном массиве.

 

Алгоритм бинарного поиска

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

Алгоритм бинарного поиска

1. Определить середину массива.

2. Если элемент, находящийся в середине массива, совпадает с искомым, поиск завершен.

3. Если элемент из середины массива больше искомого, применить бинарный поиск к первой половине массива.

4. Если элемент из середины массива меньше искомого, бинарный поиск необходимо применить ко второй половине массива.

5. Пункт 1-4 повторять, пока размер области поиска не уменьшается до нуля. Если это произойдет — ключа в массиве нет.