title: How many comparisons will binary search make in the worst case using this algorithm?
body: <p>Hi there below is the pseudo code for my binary search implementation:</p>
  
  <pre><code>Input: (A[0...n-1], K)
  begin
     l ← 0; r ← n-1
     while l ≤ r do
        m ← floor((l+r)/2)
        if K &gt; A[m] then l ← m+1
        else if K &lt; A[m] then r ← m-1 else return m
        end if 
     end while
     return -1 // key not found
  end
  </code></pre>
  
  <p>I was just wondering how to calculate the number of comparisons this implementation would make in the worst case for a sorted array of size n?</p>
  
  <p>Would the number of comparisons = lg n + 1? or something different?</p>