Binary Search

Given a sorted array arr and a target value, return the index of the target using recursive binary search. If not found, return None. Input: arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target = 23 → Output: 5.

Binary search exploits sorted order to eliminate half the search space with each comparison. Compare target to the middle element $\text{arr}[\text{mid}]$: if equal, found; if $\text{target} > \text{arr}[\text{mid}]$, search right half; otherwise left half. Each recursive call works on a shrinking window of size $\lfloor N/2 \rfloor$.

1. Base case: if left > right, return None (target not found).
2. Calculate $\text{mid} = \lfloor (\text{left} + \text{right}) / 2 \rfloor$.
3. If arr[mid] == target, return mid.
4. If arr[mid] < target, recurse on right: binary_search(arr, target, mid + 1, right).
5. If arr[mid] > target, recurse on left: binary_search(arr, target, left, mid - 1).

• Using (left + right) / 2 instead of // (returns a float in Python)
• Forgetting the base case left > right, causing infinite recursion
• Applying binary search to an unsorted array — produces incorrect results silently
• Off-by-one: searching left uses right = mid - 1, right uses left = mid + 1

Binary search reduces $O(N)$ linear search to $O(\log N)$. For 1 billion elements, that is ~30 comparisons instead of 1 billion. The iterative version (using while) is preferred in practice to avoid the $O(\log N)$ stack overhead.