Бинарный (двоичный) поиск

Данный поиск называется делением пополам (метод дихотомии). Тоже выполняется в упорядоченных массивах, для элементов которого выполняется условие (1). Х - аргумент поиска.

Определяется m=N/2 - целая часть. Рассматривается А[m]- срединный элемент исходной последовательности. Если А[m]=Х, то поиск закончен, он результативен. Если А[m]<Х, то из поиска исключаются все элементы, от А[1] до А[m], т.к. они заведомо меньше Х. Если А[m]>Х, то из поиска исключаются все элементы, от А[m] до А[n]. Поиск продолжается в оставшейся подпоследовательности (половине): определяется значение m -индекс элемента, и если его ключ не равен Х, то из поиска исключаются одна из половинок и т.д.

Пусть дан упорядоченный массив из 10 элементов (N=10):

1 2 3 4 5 6 7 8 9 10

Пусть необходимо в данном массиве найти цифру 6. Определяем m=10/2=5.

Рассматриваем A[5]=5 (А[m]). В данном случае А[m] не равно искомому элементу (5 не равно 6), и проверяем А[m]<Х? Условие выполняется (5<6) и из поиска исключаются все элементы от 1 до 5. Поиск продолжается в оставшейся половинке.

6 7 8 9 10 (N=5)

Определяем m=5/2=2 (целая часть). Рассматриваем А[2]=7. Так как А[m]>Х (7>6), то из поиска исключаются все элементы от 7 до 10. Поиск продолжается в последовательности элементов, в данном случае состоящей из одного элемента равного 6, который и является аргументом поиска. Поиск закончен.

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

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