Ile porównań przeprowadzi wyszukiwanie binarne w najgorszym przypadku przy użyciu tego algorytmu?
Cześć, poniżej znajduje się pseudo kod do mojej implementacji wyszukiwania binarnego:
<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>
Zastanawiałem się tylko, jak obliczyć liczbę porównań, które ta implementacja zrobiłaby w najgorszym przypadku dla posortowanej tablicy o rozmiarze n?
Czy liczba porównań = lg n + 1? czy coś innego?