Recursive Binary Search in Python: O(log n) with O(log n) Space
You've seen binary search implemented with a while loop. Now you'll implement the same algorithm using recursion — calling a function on a smaller sub-problem until you hit a base case. Both approaches produce identical results; the recursive version trades the explicit loop for the call stack. Understanding both is valuable, since interviewers will ask for either.
Recursion vs. Iteration: The Key Difference
- Iterative: a loop shrinks the search window by updating
leftandrightpointers. - Recursive: each function call operates on a smaller portion of the array, with the base case terminating the recursion.
The logic is identical — only the structure differs.
Designing the Recursive Function
The recursive helper needs to know which slice of the array to search. Pass left and right as parameters:
- Base case: if
left > right, the window is empty — return -1. - Recursive case: check the midpoint, then call yourself on the left or right half.
Code Implementation
def binary_search(nums, value):
def helper(left, right):
if left > right: # base case: empty window
return -1
mid = left + (right - left) // 2
if nums[mid] == value:
return mid # found it
elif nums[mid] < value:
return helper(mid + 1, right) # search right half
else:
return helper(left, mid - 1) # search left half
return helper(0, len(nums) - 1)
# Examples:
print(binary_search([1, 2, 4, 5], 4)) # 2
print(binary_search([1, 2, 4, 5], 3)) # -1
print(binary_search([], 4)) # -1
print(binary_search([7], 7)) # 0
Tracing a Recursive Call
# Array: [1, 2, 4, 5], target = 4
# helper(0, 3) → mid=1 → nums[1]=2 < 4 → call helper(2, 3)
# helper(2, 3) → mid=2 → nums[2]=4 == 4 → return 2 ✓
Complexity Analysis
- Time: O(log n) — The search space halves with each recursive call, giving at most log₂(n) + 1 calls total.
- Space: O(log n) — Each recursive call adds a frame to the call stack. With log₂(n) calls maximum, the stack depth is O(log n). This is the cost compared to the iterative O(1) space version.
The Base Case Is Everything
In recursive algorithms, the base case is what prevents infinite recursion. Here are the two base cases:
left > right— the search window collapsed without finding the target → return-1.nums[mid] == value— found the target → returnmid.
Forgetting the left > right check is the most common bug — it causes a RecursionError (Python's version of a stack overflow).
Edge Cases
assert binary_search([1, 2, 4, 5], 4) == 2 # found in middle
assert binary_search([1, 2, 4, 5], 3) == -1 # not present
assert binary_search([], 4) == -1 # empty array
assert binary_search([1], 1) == 0 # single element found
assert binary_search([1], 2) == -1 # single element not found
assert binary_search([1, 2, 4, 5], 1) == 0 # found at start
assert binary_search([1, 2, 4, 5], 5) == 3 # found at end
print("All tests passed!")
When to Use Recursive vs. Iterative
- Iterative is preferred in production Python code — it uses O(1) space and avoids hitting Python's default recursion limit (~1000 frames).
- Recursive is valuable as a learning exercise and may be more natural when the problem is inherently recursive (e.g., searching a tree).
Key Takeaways
- Recursive binary search calls itself on the left or right half — same logic as iterative, different structure.
- Time: O(log n). Space: O(log n) due to the call stack (vs. O(1) for iterative).
- Always define a clear base case (
left > right) to prevent infinite recursion. - Pass
leftandrightas parameters to define the current search window.
What to Learn Next
Now that you've implemented binary search both iteratively and recursively, push further with advanced variations: finding the first or last occurrence of a duplicated value, searching a rotated sorted array, and binary search on the answer — a powerful technique where you binary search on possible answers rather than on the array itself.
