Locate a Target's Index in a Sorted Array Using Recursive Halving
Solve this Problemnums and a value target, find the index of target in the array using recursion — or return -1 if it isn't present.
Sortedness turns "which half could possibly contain the target?" into a question answerable in O(1): compare the target against the middle element, and an entire half of the array can be ruled out immediately, no matter how large the array is. Express that as a recursive call on whichever half survives, narrowing the window (given by a low and high bound) with every call, until either the target is found or the window collapses to nothing (the base case). Each call does a constant amount of work and halves the remaining search space, so the total number of calls needed is O(log n) — a linear scan's worst case shrinks to a logarithmic one, purely by using the fact that the array is sorted.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 15 - ◆
nums is sorted in strictly increasing order - ◆
-100 ≤ nums[i], target ≤ 200 - ◆
Return the index of target if it exists, or -1 otherwise
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Linear Scan
BruteCheck every element from the start until one matches the target. This works on any array, sorted or not — but it never takes advantage of the fact that this particular array is sorted, so it can end up checking nearly every element even when the target turns out to be near the end.
O(n)O(1)1class Solution {
2 public int binarySearchRecursive(int[] nums, int target) {
3 for (int i = 0; i < nums.length; i++) {
4 if (nums[i] == target) return i;
5 }
6 return -1;
7 }
8}Optimal — Recursive Binary Search
OptimalBecause the array is sorted, checking the middle element rules out an entire half of the array at once: if the middle is too small, the target (if present) must be somewhere to the right; if it's too big, the target must be somewhere to the left. Express that as a recursive call on the surviving half, with the base case being an empty window (search space exhausted, target not found). Each call does O(1) work and shrinks the window by half, giving O(log n) calls total.
O(log n)O(log n) call-stack space1class Solution {
2 public int binarySearchRecursive(int[] nums, int target) {
3 return search(nums, target, 0, nums.length - 1);
4 }
5
6 private int search(int[] nums, int target, int lo, int hi) {
7 if (lo > hi) return -1;
8 int mid = lo + (hi - lo) / 2;
9 if (nums[mid] == target) return mid;
10 if (nums[mid] < target) return search(nums, target, mid + 1, hi);
11 return search(nums, target, lo, mid - 1);
12 }
13}