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?

Antworten auf die Frage(3)

Ihre Antwort auf die Frage