🎓 A1Learner
🔍
0 of 100 lessons completed

DSA Binary Search, Recursively

Recursive binary search halves a sorted list by calling itself on the surviving half. Each call handles a smaller range than its caller.

One call, one step

The function checks the middle value once. A larger target sends the call right.

nums = [3, 6, 9, 12, 15, 18, 21]

def search(lo, hi, target, depth):
    print("call lo =", lo, "hi =", hi, "depth =", depth)
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        return search(mid + 1, hi, target, depth + 1)
    return search(lo, mid - 1, target, depth + 1)

print("index:", search(0, 6, 21, 1))

Example

nums = [3, 6, 9, 12, 15, 18, 21]

def search(lo, hi, target, depth):
    print("call lo =", lo, "hi =", hi, "depth =", depth)
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        return search(mid + 1, hi, target, depth + 1)
    return search(lo, mid - 1, target, depth + 1)

print("index:", search(0, 6, 21, 1))
print("index:", search(0, 6, 10, 1))

Key points

  • A base case is the input where the function stops calling itself.
  • The base case here is an empty range, where lo passes hi.
  • Each call checks one middle value.
  • The surviving half becomes the range of the next call.
  • Halving keeps the call depth small, at four calls in the trace below.

In this example, the search for 21 moves right twice and lands in three calls. The search for 10 narrows to an empty range. The empty range is the base case and returns -1. The deepest trace reaches four calls, far below any limit.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

What is the base case of recursive binary search?