Привет, ниже приведен псевдокод для реализации бинарного поиска:
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? или что-то другое?
В худшем случае в этом случае, если элемент K отсутствует в и меньше всех элементов в A. Тогда мы имеем два сравнения на каждом шаге: K > A[m] и K < A[m].
Для каждого шага массив разбивается на две части, каждая из которых имеет размер (n-1)/2, мы имеем максимум шагов log_2(n-1).
Это приводит к сумме сравнений 2*log_2(n-1), которые асимптотически действительно равны O(log(n)).
Очень незначительная коррекция hielsnoppe answer:
В массиве n -element (n > 0) сравниваемый элемент имеет индекс m = floor((n-1)/2). Таким образом, есть три возможности
A[m] < K, то после одного сравнения поиск продолжается в массиве n-1-m = ceiling((n-1)/2) -element.A[m] > K, то после двух сравнений поиск продолжается в массиве m -element.A[m] == K, тогда мы закончим после двух сравнений.Итак, если мы обозначим максимальное (наихудшее) количество сравнений для поиска в массиве n -element на 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)
или
C(n) = 2*log2(n+1) + floor(2*(n+1)/(3*2^floor(log2(n+1)))).
Это точная верхняя граница.
Согласно странице wikipedia на бинарный поиск, наихудшая производительность этого алгоритма 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, где >>> - это беззнаковый оператор сдвига вправо. Подробнее о проблеме в здесь.