Rambler's Top100

Билет 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

 

Вверх

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ Faststart - рейтинг сайтов, каталог интернет ресурсов, счетчик посещаемос­ти Яндекс.Метрика
Hosted by uCoz