title: How to find running time of recursive binary search?
body: <p>For each of the procedures below, let T (n) be the running time. Find the order of T (n) (i.e., find f(n) such that T (n) ∈ (f(n)).</p>
  
  <pre><code>Procedure BinarySearch(table T [a . . . b], int k):
   if a &gt; b then
    return -1
   end if
   middle ← ⌊(a + b)/2⌋
   if T [middle] = k then
    return middle
   end if
   if k &lt; T [middle] then
    return BinarySearch(T [a . . .middle], k)
   else
    return BinarySearch(T [middle . . . b], k)
   end if
  </code></pre>
  
  <p>I know how to find run times of simple functions but since this includes recursive calls so I'm having trouble.</p>