Binary Search (Recursive)

Binary search written with recursion — each call holds one [lo, hi] window on the call stack, so the stack depth is the log-n comparison count.

Category: Searching
Time complexity: O(log n)
Space complexity: O(log n)

Pseudocode

search(lo, hi):
  if a[mid] = t: return mid
  recurse into the half with t
return via the stack

Reference implementation

def bsearch(a, lo, hi, t):
    if lo &gt; hi: return -1
    mid = (lo + hi) // 2
    if a[mid] == t: return mid
    if a[mid] &lt; t: return bsearch(a, mid+1, hi, t)
    return bsearch(a, lo, mid-1, t)

Open the interactive Binary Search (Recursive) visualisation →