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 What usually goes wrong. What you see What caused it How to fix it --- --- --- The program hangs, then dies with StackOverflowError A half was passed with mid still inside it, so the range never actually shrinks Recurse with mid - 1 as the new high or mid + 1 as the new low Values th

Challenge: Recursive Binary Search