Билет 21. Вопрос 1. Метод бинарного поиска элементов в массиве.
В программировании бинарный поиск применяется для нахождения элемента Х в отсортированном массиве. Встречаются другие названия этого метода поиска: двоичный, логарифмический, метод деления пополам, дихотомия. Основная идея заключается в следующем. Пусть массив, состоящий из N элементов, отсортирован в порядке убывания. Находим средний элемент массива А[m] , где m=(N+1) div 2 . Сравниваем его с элементом Х. Если средний элемент равен Х, то поиск заканчивается. Если же он меньше Х, то все элементы с индексами большими или равными m можно не рассматривать. Если же средний элемент больше Х, то исключаются элементы с индексами, меньшими или равными m. При выполнении этого алгоритма на каждом шаге пересчитываются границы поиска. Так на первом шаге левая граница - L=1, правая - R=N. На втором шаге либо левая, ибо правая граница поменяют свое значение. Поиск будет продолжатся до тех пор пока элемент не будет найден, либо пока левая и правая граница поиска не совпадут, что соответствует отсутствию элемента в массиве.
Фрагмент программы на Паскале имеет следующий вид:
L:=1; R:=N; P:=false; WHILE (L<=R) AND (P=FALSE) DO begin M:=(R+ L) DIV 2; IF A[M]=X THEN P:=TRUE ELSE IF A[M]>X THEN L:=M+1 ELSE R:=M-1 end; После выполнения цикла номер элемента, равного Х, хранится в переменной R. Если R<L, значит совпадений нет. Пусть К - количество операций сравнения, которые необходимы для нахождения элемента в упорядоченном массиве методом бинарного поиска. Число К определяется из следующего неравенства: N<=2 K . Отсюда К можно вычислить по формуле: К=[log 2 N]+1
|