Джастин был неправ.Общий алгоритм binarySearch сначала проверяет, равна ли цель текущему среднему элементу, прежде чем перейти к левой или правой половине, если это необходимо.Ленивый алгоритм binarySearch откладывает проверку на равенство до самого конца.
algorithm lazyBinarySearch(array, n, target)
left<-0
right<-n-1
while (left<right) do
mid<-(left+right)/2
if(target>array[mid])then
left<-mid+1
else
right<-mid
endif
endwhile
if(target==array[left])then
display "found at position", left
else
display "not found"
endif
В вашем случае, в массиве,
2 11 13 21 44 50 69 88
, и вы хотите найти 11
Сначала мы выполняем трассировку обычного двоичного поиска,
index 0 1 2 3 4 5 6 7
2 11 13 21 44 50 69 88
left mid right
Первый цикл while:
left <= right, мы входим в первый цикл while.Мы вычислили средний индекс на (0 + 7) /2=3.5=3 целочисленным делением, mid = 3. <strong>сразу мы проверяем, равна ли цель 11 входу среднего индекса, 11! = 21, затем мы решаем, идти ли налево или направо, мы узнаем, что 11 <21, должны идти налево.левый индекс остается неизменным, правый индекс становится средним индексом -1, правый = 3 - 1 = 2. Выполнен этот шаг. </p>
Второй цикл while:
left <= right, 0 <= 2входим во второй цикл.Средний индекс пересчитывается: (0 + 2) / 2 = 1, средний = 1. <strong>Сразу мы делаем проверку на равенство, цель 11 совпадает с записью индекса 1, 11 == 11. Мынашел эту запись, оставив позади все левые и правые средние индексы (пофиг) и разрывая цикл while, возвращая индекс 1.
Теперь мы отслеживаем этот поиск по ленивому алгоритму binazySearch, исходный массив с левой /правильные индексы настроены так же, как и предыдущие.
Первый цикл while:
left Вместо того, чтобы проверять равенство в обычном двоичном поиске, на этот раз мы проводим сравнение со средним индексом.И сравнение только проверяет, больше ли наша цель 11, чем средняя запись индекса, оставляя равными они или нет до самого конца вне цикла while. Итак, мы обнаруживаем, что 11 <21, правый индекс сбрасывается в серединуindex, right = 3. Выполнено на этом шаге. </p>
Второй цикл while:
left Снова мы проводим сравнение со средней записью индекса 11, мы понимаем, что она не больше, чем середина записи индекса.Мы попадаем в остальную часть цикла while и сбрасываем правый индекс на средний индекс, right = 1. Выполнен этот шаг.
Третий цикл while:
left 2), левый индекс сбрасывается до середины + 1, левый =0 + 1 = 1. Выполните этот шаг.
С левым индексом = 1 и правым индексом = 1, левым = правым, в то время как условие цикла больше не выполняется, поэтому нет необходимости повторно вводить.Мы падаем в часть if внизу.Цель 11 равна записи левого индекса 11, мы нашли цель и возвращаем левый индекс 1.
Как вы можете видеть, ленивый binarySearch делает еще один шаг цикла, чтобы наконец понять, что индекс на самом деле равен 1. И вот какСлово «откладывает проверку на равенство» означает в определении, которое я упомянул в самом начале.Очевидно, что ленивый алгоритм binarySearch делает больше вещей, чем обычный binarySearch, до достижения завершения программы. И термин "ленивый" отражается во время, когда проверка цели равна средней записи индекса.
Однако ленивый binarySearch предпочтительнее использовать при некоторых других обстоятельствах, но этоне в контексте этого случая.
(аргументирующая часть алгоритма сделана мной, кто-то хочет скопировать, пожалуйста, сделайте кредит)
источник: «Структуры данных вне в Java»Сеш Венугопал, Прентис Холл