Problem Statement
The task is to implement binary search using recursion to find the index of a target element in a sorted array.
Definition
- Binary search is a searching algorithm that divides the search range in half with each step, reducing the time complexity compared to linear search.
- Example: For the input
[1, 2, 3, 4, 5] and target 4, the output should be 3 (the index of 4 in the array).
Example Inputs
- Input:
[1, 2, 3, 4, 5], target = 4
- Output: 3
Explanation: The target element 4 is at index 3 in the array.
Approach - Use Recursion
Approach
Binary search works by dividing the array into halves:
- Compare the target element with the middle element of the array.
- If the target matches the middle element, return the index.
- If the target is smaller than the middle element, recursively search the left half.
- If the target is larger than the middle element, recursively search the right half.
- Repeat the process until the target is found or the search range becomes empty.
Steps
- Define the base case: If the left index exceeds the right index, the target is not in the array.
- Calculate the middle index as
mid = Math.floor((left + right) / 2).
- Compare the target with the middle element:
- If
arr[mid] === target, return mid.
- If
arr[mid] > target, search the left half (left to mid - 1).
- If
arr[mid] < target, search the right half (mid + 1 to right).
- Return the index of the target if found; otherwise, return
-1.
Time & Space Complexity
- Time Complexity: O(log n), where
n is the size of the array. The search range is halved at each step.
- Space Complexity: O(log n), due to the recursion stack.
Code Snippet
Dry Run
Let’s dry run the code with the input arr = [1, 2, 3, 4, 5] and target = 4:
- binarySearch([1, 2, 3, 4, 5], 4, 0, 4):
- Middle index:
mid = Math.floor((0 + 4) / 2) = 2.
- Compare
arr[2] (3) with target (4): 3 < 4, search the right half.
- binarySearch([1, 2, 3, 4, 5], 4, 3, 4):
- Middle index:
mid = Math.floor((3 + 4) / 2) = 3.
- Compare
arr[3] (4) with target (4): Match found, return 3.
Output:
- Result: 3 (the index of
4 in the array).
Complexity Analysis
Time and Space Complexity
- Time Complexity: O(log n) because the search range is halved with each step.
- Space Complexity: O(log n) due to the recursion stack. The depth of the recursion depends on the size of the array.
Conclusion
Binary search is an efficient algorithm for searching in sorted arrays, significantly reducing the number of comparisons compared to linear search. The recursive implementation is elegant and easy to understand, though it comes with a space overhead due to the recursion stack. For larger arrays, an iterative approach may be more space-efficient, but recursion provides a clean and concise solution for this problem.