Recursive-Binary-Search

Programmer's Picnic — Binary Search ( Recursive)

Learn both styles and understand recursion vs iteration tradeoffs.

Self-study • Intermediate

Date: [Replace with date]
Time: [Replace with time & timezone]

See Code Compare Take Quiz

Quick idea

Same binary-splitting idea; recursive version calls itself on left or right half, iterative uses a loop.

Python — Iterative

def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (right + left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
  

Python — Recursive

def binary_search_recursive(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)
  

Both return the index if found or -1 if not.

Recursion: what changes?

• Time: still O(log n).
• Space: recursive calls use call stack → O(log n) extra space proportional to recursion depth.
• Readability: recursion can look cleaner for divide-and-conquer solutions; iterative avoids stack overhead.
• Tail recursion: Python doesn't optimize tail calls — iterative is often preferred in Python for large inputs.

Dry-run (recursive)

arr=[2,5,7,10,13,18], target=13

1. call(0,5): mid=2 → arr[2]=7 < 13 → recursive call(3,5)
2. call(3,5): mid=4 → arr[4]=13 → found → return 4

When to use which?

• Use iterative when memory is a concern or input size is large.
• Use recursive for clearer code if input sizes are moderate and recursion depth isn't dangerous.
• In Python, iterative is generally safer for production because Python recursion depth is limited.

MCQ — 5 (Iterative + Recursive)

1. Recursive binary search extra space complexity?

O(1)
O(log n)

2. Both iterative and recursive binary search time complexity?

O(n)
O(log n)

3. Which one can cause recursion depth problems in Python?

Iterative
Recursive

4. For huge input lists, pick:

iterative
recursive

5. Both versions require sorted array?

Yes
No

Small Exercises

1. Modify the recursive version to return the leftmost index when duplicates exist.
2. Measure runtime of iterative vs recursive on large arrays (timeit).
3. Implement binary search for descending-sorted arrays (reverse comparison).

Prepared by Champak Roy — Programmer's Picnic series.