Recursive Binary Search

Part of: Recursion

Searching by Halving Binary search finds a target in a sorted array by repeatedly cutting the search range in half. Recursion expresses this beautifully: each call searches a sub-range defined by low and high indices. The Algorithm - Compute the middle index mid = (low + high) / 2. - If arr[mid] equals the target, return mid. - If the target is smaller , search the left half (low..mid-1). - If the target is larger , search the right half (mid+1..high). - Base case : if low high, the range is empty, the target is not present, return -1. Why It Is Fast Each call eliminates half of the remaining elements, so binary search runs in O(log n) time. Searching 1,000,000 sorted items takes about 20 comparisons. Linear search would take up to a million. Tracing an Example Search for 7 in {1, 3, 5, 7, 9} with low=0, high=4: - mid=2, arr[2]=5; 7 5 - search right low=3, high=4 - mid=3, arr[3]=7 - found, return 3 Critical Requirement Binary search only works on sorted data. On unsorted input it gives wrong answers. The base case low high is what guarantees termination: every recursive call strictly shrinks the range, so it cannot loop forever.

Challenge: Recursive Binary Search