Как сравнить максимальный ключ в бинарном поиске (1 + log (n)), а не log (n)?

Question

Я перебирал более универсальное объяснение BS. Который имеет предлог, что максимальное число ключей сравнения в двоичном поиске равно (1 + log (n)). Я попытался сформировать интуицию относительно того, как это возможно. Я понимаю, что время разрушения BS (log (n)). Также я предполагаю, что худший поиск по времени / максимальному ключу произойдет в сценарии, когда мы будем искать элемент, которого нет в массиве. Но каждый раз, когда i go над гипотетическим массивом, выполняющим BS, я в конечном итоге (log (n)) сравнивает / делает шаги больше, чем это. Вот код, который использовался для формирования этого предлога.

public static int binarySearch(int[] a, int key){
     int lo = 0, hi = a.length-1;
     while (lo <= hi){
         int mid = lo + (hi - lo) / 2;

         if (key < a[mid]) 
            hi = mid - 1;
         else if (key > a[mid]) 
            lo = mid + 1;
         else 
            return mid;
     }
     return -1;
 }

Возможно, мои предположения неверны или я упускаю какую-то точку. Если бы вы могли объяснить, как максимально возможное сравнение ключей будет (1 + log (n)), было бы здорово, спасибо.

Answer 1

Не забывайте, что даже если у вас есть только 1 элемент, вам все равно придется угадать его, поскольку вполне возможно, что цель не находится в массиве. Поэтому нам нужно добавить +1 к последнему предположению, когда мы дошли до последнего оставшегося элемента.

Это может быть понятнее, если подумать, когда n=1. Нам все еще нужно 1 предположение, но log_2(1) = 0. Поэтому нам нужно добавить +1, чтобы исправить формулу.

Когда n не является степенью 2, мы можем просто go до следующей более высокой степени 2. Для массива длина которого равна 1000, следующая более высокая степень 2 равна 1024, что равно 10. Поэтому для массива из 1000 элементов бинарный поиск потребует не более 11 (10 + 1) догадок.

Почему?

В худшем случае для бинарного поиска потребуется 10 шагов, чтобы отделить оставшиеся числа, и 1 последний шаг, чтобы проверить, является ли оставшееся только одно число Вы хотите, или это не в массиве.

Answer 2

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

   +-----+-----+-----+-----+-----+
   |  0  |  1  |  2  | ... | n-1 |
   +-----+-----+-----+-----+-----+

Теперь нумеруйте разделители:

   +-----+-----+-----+-----+-----+
   |  0  |  1  |  2  | ... | n-1 |
   +-----+-----+-----+-----+-----+
   0     1     2     3 .. n-1    n

Обратите внимание, что существует n + 1 разделителей, один перед каждым элементом и один после самый последний элемент.

Всякий раз, когда вы выполняете двоичный поиск, вы проверяете индекс среднего разделителя (вы понимаете, почему?) и выбрасываете половину разделителей. Вы можете выбросить только половину коллекции из k предметов из журнала ₂ k раз , прежде чем перейти к одному оставшемуся элементу. Это означает, что количество необходимых зондов будет ⌈log ₂ (n + 1) ⌉, и это случай, когда

log ₂ n <⌈log <sub>2 (n + 1) log ≤ log ₂ n + 1,

, поэтому бит "1 + log n" заканчивается вверх, возникающих из-за «выбросить половину разделителей», чем из других источников.

Надеюсь, это поможет!

Answer 3

Представьте массив размером 8.

l=0, h = 7, mid =  0 + (7-0)/2 = 3   go right
l=4, h = 7, mid =  4 + (7-4)/2 = 5   go right
l=6, h = 7, mid =  6 + (7-6)/2 = 6   go right
l=7, h = 7, mid =  7 + (7-7)/2 = 7   go left  
l=7, h=6 ====> terminates

Всего сравнений = 1 + Журнал 8 = 4

РЕДАКТИРОВАТЬ1: представьте себе этот массив и используйте ручку и бумаги и проследить вышеупомянутые шаги. Поиск значения 13.

index:      0  1  2  3  4  5  6   7   
            ------------------------------
element:    1  3  5  6  7  9  11  15