Основы программирования



              

Бинарный поиск - часть 2


найти i: a[i] = x

Если же x не содержится в массиве, то надо определить индекс x, такой, что при добавлении элемента x в i-ю ячейку массива элементы массива останутся упорядоченными, т.е.

найти i: a[i-1] < x =< a[i]

(считается, что a[-1] = -?, a[n] = + ?). Объединив оба случая, получим неравенство

a[i-1] < x =< a[i]

Используем схему построения цикла с помощью инварианта. В процессе выполнения хранятся два индекса b и e (от слов begin и end), такие, что

a[b] < x =< a[e]

Индексы b и e ограничивают текущий отрезок массива, в котором осуществляется поиск. Приведенное неравенство является инвариантом цикла. Перед началом выполнения цикла рассматриваются разные исключительные случаи — когда массив пустой (n=0), когда x не превышает минимального элемента массива (x =< a[0]) и когда x больше максимального элемента (x > a[n-1]). В общем случае выполняется неравенство

a[0] < x =< a[n-1])

Полагая b = 0, e = n - 1, мы обеспечиваем выполнение инварианта цикла перед началом выполнения цикла. Условие завершения состоит в том, что длина участка массива, внутри которого может находится элемент x, равна единице:

b - e = 1

В этом случае

a[e-1] < x =< a[e]

т.е. искомый индекс i равен e, а элемент x содержится в массиве тогда и только тогда, когда x = a[e]. В цикле мы вычисляем середину c отрезка [b,e]

с = целая часть ((b+e)/2)

и выбираем ту из двух половин [b,c] или [c,e], которая содержит x. Для этого достаточно сравнить x со значением a[c] в середине отрезка. Завершение цикла обеспечивается тем, что величина e - b монотонно убывает после каждой итерации цикла.

Приведем текст алгоритма бинарного поиска:

лог алгоритм бинарный_поиск( вход: цел n, вещ a[n], вещ x, выход: цел i ) | Дано: n — число элементов в массиве a, | a[0] < a[1] < ... < a[n-1] | Надо: ответ := (x содержится в массиве), | вычислить i, такое, что | a[i-1] < x <= a[i] | (считая a[-1] = -беск., a[n] = +беск.) начало | цел b, e, c; | | // Рассматриваем сначала исключительные случаи | если (n == 0) | | то i = 0; | | ответ := ложь; | иначе если (x <= a[0]) | | i := 0; | | ответ := (x == a[0]); | иначе если (x > a[n-1]) | | i := n | | ответ := ложь; | иначе | | // Общий случай | | утверждение: a[0] < x <= a[n-1]; | | b := 0; e := n-1; | | | | цикл пока e - b > 1 | | | инвариант: a[b] < x и x <= a[e]; | | | c := целая часть((b + e) / 2); | | | если x <= a[c] | | | | то e := c; | | | иначе | | | | b := c; | | | конец если | | конец цикла | | | | утверждение: e - b == 1 и | | a[b] < x <= a[e]; | | i := e; | | ответ := (x == a[i]); | конец если конец алгоритма




Содержание  Назад  Вперед