Индивидуальное задание

Лабораторная работа 7

ДВОИЧНЫЙ ПОИСК

· В программировании бинарный поиск применяется для нахождения элемента Х в отсортированном массиве. Встречаются другие названия этого метода поиска: двоичный, логарифмический, метод деления пополам, дихотомия.

· Основная идея заключается в следующем.

· Пусть массив, состоящий из N элементов, отсортирован в порядке убывания. Находим средний элемент массива А[m] , где m=(N+1) div 2 . Сравниваем его с элементом Х. Если средний элемент равен Х, то поиск заканчивается. Если же он меньше Х, то все элементы с индексами большими или равными m можно не рассматривать. Если же средний элемент больше Х, то исключаются элементы с индексами, меньшими или равными m.

· При выполнении этого алгоритма на каждом шаге пересчитываются границы поиска. Так на первом шаге левая граница - L=1, правая - R=N. На втором шаге либо левая, ибо правая граница поменяют свое значение. Поиск будет продолжатся до тех пор пока элемент не будет найден, либо пока левая и правая граница поиска не совпадут, что соответствует отсутствию элемента в массиве.

Алгоритм имеет следующий вид:

flag = «ложь»;

L=0;

R=N-1;

Начало цикла 1: выполнять пока (L ≤ R) и (flag = =«ложь»);

m=(R+L)/2;

если(a[m] = = X)

тогда

flag = «истина»;

иначе

если a[m]>X

тогда

R=m+1;

иначе

L=m-1;

все

конец цикла 1

Если (flag= = true) то

печать сообщения: «Элемент Х найден, его номер - m»,

иначе печать: «Элемента Х нет!»,

ПримеркоданаязыкепрограммированияCидляпоискаэлементаxвмассивеa[n], отсортированноговвозрастающемпорядке:

size_tfirst=0;/* Номер первого элемента в массиве */

size_tlast=n;/* Номер элемента в массиве, СЛЕДУЮЩЕГО ЗА последним */

/* Если просматриваемый участок непустой, first<last */

size_tmid;

if(n==0)

{

/* массив пуст */

}

elseif(a[0]>x)

{

/* не найдено; если вам надо вставить его со сдвигом - то в позицию 0 */

}

elseif(a[n-1]<x)

{

/* не найдено; если вам надо вставить его со сдвигом - то в позицию n */

}

while(first<last)

{

/* ВНИМАНИЕ! В отличие от более простого (first+last)/2, этот код стоек к переполнениям.

Если first и last знаковые, возможен код (unsigned)(first+last) >> 1. */

mid=first+(last-first)/2;

if(x<=a[mid])

{

last=mid;

}

else

{

first=mid+1;

}

/* Если условный оператор if(n==0) и т.д. в начале опущен - значит, тут раскомментировать! */

if(/* last<n &&*/a[last]==x)

{

/* Искомый элемент найден. last - искомый индекс */

}else

{

/* Искомый элемент не найден. Но если вам вдруг надо его вставить со сдвигом, то его место - last. */

}

Несмотрянато, чтокоддостаточнопрост, внёместьнескольколовушек.

Чтобудет, еслиfirstиlastпоотдельностиумещаютсявсвойтип, аfirst+last — нет?
Будетлиработатьнапустоммассиве (n=0)?
Способенликоднаходитьотсутствующиезначения? Унекоторыхпрограммистовнаписанный «слиста» двоичныйпоисквтакойситуациизацикливается — иониэтогонеосознают, покатестированиенедастошибку.
Иногдатребуется, чтобы, еслиxвцепочкесуществуетвнесколькихэкземплярах, находилонелюбой, аобязательнопервый (каквариант:последний; следующийзапоследним). Даннаяверсиякодавтакойситуациинаходитпервыйизравных.

УчёныйЙонБентлиутверждает, что90% студентов, разрабатываядвоичныйпоиск, забываютучестькакое-либоизэтихтребований. Идажевкод, написанныйсамимЙономиходившийизкнигивкнигу, вкраласьошибка:коднестоеккпереполнениям.

Приложения

Практическиеприложенияметодадвоичногопоискаразнообразны:

Широкоераспространениевинформатикеприменительнокпоискувструктурахданных. Например, поисквмассивахданныхосуществляетсяпоключу, присвоен-номукаждомуизэлементовмассива (впростейшемслучаесамэлементявляетсяключом).
Такжеегоприменяютвкачествечисленногометодадлянахожденияприближённогорешенияуравнений.
Методбисекциииспользуетсядляпоискачисленныхрешенийуравнений.
Методиспользуетсядлянахожденияэкстремума целевойфункцииивэтомслучаеявляетсяметодомусловнойодномернойоптимизации. Когдафункцияимеетвещественныйаргумент, найтирешениесточностьюдо $\varepsilon$ можнозавремя $\log_2 1 / \varepsilon$ . Когдааргументдискретен, иизначальнолежитнаотрезкедлины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

[Вверх] [В начало]