160
элемента отсортированного списка с заданным ключевым значением возможен
один из следующих трёх случаев: 1) значение серединного элемента равно
заданному ключевому значению; 2) значение серединного элемента меньше
заданного ключевого значения; 3) значение
серединного элемента больше
заданного ключевого значения; Первый случай является наилучшим, и задача
поиска решена: серединный элемент является искомым элементом. Во втором
случае становится ясным, что искомый элемент, если он имеется в списке, находится
до рассматриваемого серединного элемента, дальнейший поиск необходимо
осуществлять в
половине списка, расположенной до серединного элемента. Вторая
же половина списка, расположенная после серединного элемента. исключается из
дальнейшего рассмотрения, так как в ней не содержится искомый элемент. В
третьем случае искомый элемент может находиться после рассматриваемого
серединного элемента и дальнейший поиск необходимо осуществлять в половине
списка, расположенной после серединного элемента.
Другая же половина списка,
расположенная до серединного элемента. исключается из дальнейшего
рассмотрения, так как в ней не содержится искомый элемент.
Рассмотрим пример практической реализации бинарного алгоритма поиска
элемента одномерного массива с заданным значением. Пусть задан упорядоченный
массив A[9]={6,12,18,42,44,56,67,94,100} (1)
и требуется определить элемент с заданным значением 56 (key=56 - ключ).
Индекс элемента A[0]=6, являющегося левым граничным элементом массива, равен
0 (l=0, left – левый). Индекс элемента A[8]=100, являющегося правым граничным
элементом массива, равен 8 (r=8, right – правый). Серединным элементом массива
(1) является элемент A[4]=44 с индексом 4 (mid= (l+r)/2= (0+8)/2=4, middle –
середина), назовём его явным серединным элементом. Используя серединный
элемент A[mid]=A[4]=44, массив (2) можно расписать в виде A[9]={6, 12, 18, 42} {44} {
56, 67, 94, 100}. (2)
Так как 44<56, искомый элемент будем искать в подмассиве
элементов,
находящихся после серединного элемента A[4]=44, а именно в подмассиве V
1
={56, 67,
94, 100}, а серединный элемент A[4]=44 и подмассив V
2
={6, 12, 18, 42} элементов,
расположенных в исходном массиве (1) до него, исключаем из рассмотрения.
Подмассив V
1
={56, 67, 94, 100}, в котором может находиться искомый элемент,
