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

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

Принцип метода:

Исходный массив делится пополам и для сравнения выбирается средний элемент. Если он совпадает с искомым, то поиск заканчивается.

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

Аналогично, если средний элемент больше искомого, то отбрасывается правая часть, а остается левая.

На втором этапе выполняется аналогичные действия над оставшейся половиной массива. В результате после второго этапа остается ¼ часть массива.

И так далее, пока или элемент будет найден, или длина зоны поиска станет равной 0. В последнем случае искомый элемент найден не будет.

Пример 3. Пусть дан массив А из n элементов, который отсортирован по возрастанию: . Искомый элемент обозначит как x. Индекс левого элемента области поиска обозначим как l, индекс правого элемента – r, а индекс среднего элемента – m.

Пусть х=5. Рассмотрим процедуру поиска по схеме.

Пусть х=-1. Рассмотрим процедуру поиска по схеме.