Как вы вычисляете большую часть алгоритма двоичного поиска?

Question

Я ищу математическое доказательство, а не просто ответ.

Answer 1

Отношение повторения бинарного поиска составляет (в худшем случае)

T(n) = T(n/2) + O(1)

Использование Теорема магистра

• n - размер проблемы.
• a - количество подзадач в рекурсии.
• n / b - размер каждой подзадачи.(Здесь предполагается, что все подзадачи, по сути, имеют одинаковый размер.)
• f (n) - это стоимость работы, выполненной вне рекурсивных вызовов, которая включает стоимость деления проблемы и стоимость объединениярешения подзадач.

Здесь a = 1, b = 2 и f (n) = O (1) [Константа]

Мы имеем f (n) = O(1) = O (n ^{log _b a} )

=> T (n) = O (n ^{log _b a} log ₂ n)) = O (log ₂ n)

Answer 2

Доказательство довольно простое: с каждой рекурсией вы вдвое уменьшаете количество оставшихся предметов, если вы еще не нашли предмет, который искали. И так как вы можете только рекурсивно разделить число n на половины не более log ₂ ( n ) раз, это также граница для рекурсии:

2 · 2 ·… · 2 · 2 = 2 ^x ≤ n ⇒ log ₂ (2 ^x ) = x ≤ log ₂ ( n )

Здесь x также число рекурсий. А при локальной стоимости O (1) это O (log n ) в общей сложности.