Wie viele Vergleiche führt die binäre Suche mit diesem Algorithmus im schlimmsten Fall durch?
Hallo, unten ist der Pseudocode für meine Implementierung der binären Suche:
<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>
Ich habe mich nur gefragt, wie die Anzahl der Vergleiche berechnet werden soll, die diese Implementierung im schlimmsten Fall für ein sortiertes Array der Größe n durchführen würde.
Wäre die Anzahl der Vergleiche = lg n + 1? oder was anderes?