Сколько сравнений сделает двоичный поиск в худшем случае с использованием этого алгоритма?

Привет, ниже приведен псевдокод для моей реализации двоичного поиска:

Input: (A[0...n-1], K)
begin
   l ← 0; r ← n-1
   while l ≤ r do
      m ← floor((l+r)/2)
      if K > A[m] then l ← m+1
      else if K < A[m] then r ← m-1 else return m
      end if 
   end while
   return -1 // key not found
end

Мне просто было интересно, как рассчитать количество сравнений, которые эта реализация сделает в худшем случае для отсортированного массива размера n?

Будет ли количество сравнений = lg n + 1? или что то другое?


arrays algorithm complexity-theory binary-search
person Harry Tiron    schedule 13.05.2012    source источник
comment
В вашем коде ошибка: if K > A[m] then return l ← m+1 должно быть if K > A[m] then l ← m+1 без return.   -  person Gumbo    schedule 13.05.2012

Ответы (3)


arrow_upward
19
arrow_downward

В худшем случае в этом случае элемент K отсутствует в A и меньше всех элементов в A. Тогда у нас есть два сравнения на каждом шаге: K > A[m] и K < A[m].

Поскольку на каждом шаге массив разрезается на две части, каждая размером (n-1)/2, у нас есть максимум log_2(n-1) шагов.

Это приводит к общему количеству сравнений 2*log_2(n-1), что действительно асимптотически равно O(log(n)).

person hielsnoppe    schedule 13.05.2012
comment
В худшем случае все элементы будут одинаковыми! Таким образом, временная сложность должна быть O (n) - person Pikesh Prasoon; 31.08.2018

arrow_upward
12
arrow_downward

Очень незначительное исправление в ответе hielsnoppe:

В массиве n-элементов (n > 0) сравниваемый элемент имеет индекс m = floor((n-1)/2). Итак, есть три возможности

  1. A[m] < K, затем после одного сравнения поиск продолжается в массиве из n-1-m = ceiling((n-1)/2) элементов.
  2. A[m] > K, то после двух сравнений поиск продолжается в массиве m элементов.
  3. A[m] == K, значит, мы закончили после двух сравнений.

Таким образом, если мы обозначим максимальное (наихудшее) количество сравнений для поиска в массиве из n элементов как C(n), мы получим

C(0) = 0
C(n) = max { 1 + C(ceiling((n-1)/2), 2 + C(floor((n-1)/2) }, n > 0

Для нечетного n = 2k+1 пол и потолок идентичны, поэтому максимум, очевидно, последний,

C(2k+1) = 2 + C(k)

и даже для n = 2k находим

C(2k) = max { 1 + C(k), 2 + C(k-1) }.

Для n = 2 это разрешается в C(2) = 1 + C(1) = 1 + 2 = 3, для всех больших, даже n, максимальное значение составляет 2 + C(k-1), поскольку для n >= 1 у нас есть C(n) <= C(n+1) <= C(n) + 1.

Оценивая рекурсию для первых нескольких n, мы находим

C(0) = 0
C(1) = 2
C(2) = 3
C(3) = C(4) = 4
C(5) = C(6) = 5
C(7) = C(8) = C(9) = C(10) = 6
C(11) = ... = C(14) = 7
C(15) = ... = C(22) = 8
C(23) = ... = C(30) = 9

Итак, по индукции докажем

C(n) = 2k, if 2^k <= n+1 < 2k + 2^(k-1), and
C(n) = 2k+1, if 2^k + 2^(k-1) <= n+1 < 2^(k+1)

or

C(n) = 2*log2(n+1) + floor(2*(n+1)/(3*2^floor(log2(n+1)))).

Это точная верхняя граница.

person Daniel Fischer    schedule 13.05.2012
comment
Могу ли я сказать, что для N отсортированных элементов в худшем случае будут сравнения пола (log2 (N + 1)). Под худшим случаем я подразумеваю, что элемента нет в списке? - person rohitt; 28.02.2020

arrow_upward
6
arrow_downward

Согласно странице википедии о двоичном поиске, производительность этого алгоритма в худшем случае равна O(lg n), что измеряет асимптотическое количество необходимых сравнений. Фактическое количество сравнений в наихудшем случае будет 2*lg(n-1), как было указано в ответе @hielsnoppe.

Псевдокод в вопросе представляет собой типичную реализацию двоичного поиска, поэтому ожидаемые сложности с производительностью сохраняются для массива (или вектора) размера n:

  • Лучшая производительность: O(1)
  • Средняя эффективность обращения: O(lg n)
  • Результат наихудшего случая: O(lg n)

При ближайшем рассмотрении в вопросе есть две проблемы с псевдокодом:

  • Строка: if K > A[m] then return l ← m+1 должна читаться как if K > A[m] then l ← m+1. Ты еще не можешь вернуться
  • Строка: m ← floor((l+r)/2) может вызвать переполнение, если числа достаточно большие при работе с целыми числами фиксированного размера. Правильный синтаксис зависит от того, какой язык программирования вы используете, но что-то в этом роде решит проблему: m ← (l + r) >>> 1, где >>> - беззнаковый оператор сдвига вправо. Подробнее о проблеме см. здесь .
person Óscar López    schedule 13.05.2012