Сколько сравнений необходимо для двоичного поиска в этом массиве?

Question

У нас есть следующий массив: [4, 13, 25, 33, 38, 41, 55, 71, 73, 84, 86, 92, 97] Мне кажется, что нужно только 3 сравнения, чтобы найти 25, потому что: сначала мы выбираем средний элемент 55. Теперь мы выполняем два сравнения: 55 = 25? 55> 25? Ничто из этого не выполняется, поэтому мы идем налево от массива. Мы получаем подмассив: [4, 13, 25, 33, 38, 41] Мы снова делим это и получаем 25 = 25? да .. Итак, нам потребовалось 3 сравнения, чтобы получить наш матч. В моей книге сказано, что для того, чтобы найти 25, нужно четыре сравнения. Почему это?

Answer 1

Поскольку размер левого массива четный, каждый алгоритм может выбрать одно из средних чисел. Следовательно, сравнение может быть следующим с 4 сравнениями:

[4, 13, 25, 33, 38, 41, 55, 71, 73, 84, 86, 92, 97]
25 < 55 =>‌ [4, 13, 25, 33, 38, 41]
25 < 33 => [4, 13, 25]
25 > 13 => [25]
25 == 25 => Found.