Алгоритм поиска в упорядоченной последовательности.

Если последовательность упорядочена, т.е. значения элементов последовательности возрастают или убывают с увеличением порядковых номеров элементов, то к ней есть возможность применить другой алгоритм поиска. Стандартным методом поиска в упорядоченном массиве является метод деления отрезка пополам (алгоритм дихотомии).

В процессе такого поиска границы промежутка можно сдвинуть друг к другу. После каждого сравнения сдвигается верхняя, либо нижняя граница промежутка. Промежутком данных или отрезком является отрезок индексов от 1 до N.

Пусть значение наименьшего индекса в исходной последовательности равно А, а значение наибольшего индекса – В. Если разделить рассматриваемый интервал [A,B] пополам, получится некоторое значение С. Сравниваем X[C] с заданным значением Р. Если X[C]>P, то элемент следует искать для B = C – 1, если X[C]<P, то для А = С + 1. Следует повторять эти действия до тех пор, пока А и В не совпадут. Проверить условие X[А]=P, и по результатам проверки может быть сформирован результат.

Чтобы сбалансировать количество возможных вычислений в обоих случаях, переменную С выбирают так, что отрезки значений А-С и В-С должны быть близки.

Словесный алгоритм поиска имеет следующий вид:

1. Вычислить С.


2. Сравнить X[C] с переменной Р.


3. Определить А и В.


4. Если А и В не совпадают, повторить с п. 1.