Recursive Binary Search
Binary Search is a highly efficient algorithm for finding a target value within a sorted array. Instead of searching linearly item-by-item, it repeatedly halves the search space.
How it works recursively:
- Base Case 1 (Empty Interval): If the search pointers cross (
low > high), the element is not present. Return-1. - Mid Computation: Find the middle index:
mid = Math.floor((low + high) / 2). - Base Case 2 (Match Found): If
arr[mid] === target, the search is complete. Returnmid. - Recursive Step (Left Half): If the target is smaller than the middle element, search the left subsegment recursively:
binarySearch(arr, target, low, mid - 1). - Recursive Step (Right Half): If the target is larger, search the right subsegment recursively:
binarySearch(arr, target, mid + 1, high).
Complexity Analysis
Time Complexity: O(log N)
Each recursive call divides the search space in half. For an array of size $N$, it takes at most $\log_2 N$ steps to find the element or determine its absence.
Space Complexity: O(log N)
Since it divides the array space recursively, the maximum call stack height is $\log_2 N$, requiring logarithmic auxiliary stack space.