Сколько сравнений сделает бинарный поиск в худшем случае, используя этот алгоритм?
Привет там ниже псевдокод для моей реализации двоичного поиска:
<code>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 </code>
Мне было просто интересно, как рассчитать количество сравнений, которые эта реализация сделает в худшем случае для отсортированного массива размером n?
Будет ли количество сравнений = lg n + 1? или что-то другое?