Boundary update without `+1` / `-1`
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.
A complete visual walkthrough of the two-binary-search approach — finding both boundaries in O(log n) time.
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109nums is a non-decreasing array.-109 <= target <= 109Scan left to right to find the first occurrence, then scan right to left (or continue forward) to find the last.
int first = -1, last = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { if (first == -1) first = i; last = i; } } return new int[]{first, last};
first, last := -1, -1 for i, v := range nums { if v == target { if first == -1 { first = i } last = i } } return []int{first, last}
first, last = -1, -1 for i in range(len(nums)): if nums[i] == target: if first == -1: first = i last = i return [first, last]
let (mut first, mut last) = (-1i32, -1i32); for (i, &v) in nums.iter().enumerate() { if v == target { if first == -1 { first = i as i32; } last = i as i32; } } return vec![first, last];
let first = -1, last = -1; for (let i = 0; i < nums.length; i++) { if (nums[i] === target) { if (first === -1) first = i; last = i; } } return [first, last];
This runs in O(n) time. If every element is the target, we touch all n elements. The problem requires O(log n), so we need binary search.
Key observation: A standard binary search finds any occurrence of the target. But we need the first and last specifically. The trick is to run binary search twice, with a subtle difference in how we handle equality.
Both searches look identical except for one critical line — what happens when nums[mid] == target.
Same structure, opposite directions. When we find a match, a normal binary search would stop. But we "continue past" the match — leftward for findFirst, rightward for findLast — to ensure we reach the boundary. The result variable remembers the best match found so far.
Target = 8. Expected result: [3, 4].
| Iter | lo | hi | mid | nums[mid] | Action | result |
|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 7 | 7 < 8 → lo = 3 | -1 |
| 2 | 3 | 5 | 4 | 8 | 8 == 8 → result=4, hi = 3 | 4 |
| 3 | 3 | 3 | 3 | 8 | 8 == 8 → result=3, hi = 2 | 3 |
| — | 3 | 2 | — | — | lo > hi → done | 3 |
| Iter | lo | hi | mid | nums[mid] | Action | result |
|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 7 | 7 < 8 → lo = 3 | -1 |
| 2 | 3 | 5 | 4 | 8 | 8 == 8 → result=4, lo = 5 | 4 |
| 3 | 5 | 5 | 5 | 10 | 10 > 8 → hi = 4 | 4 |
| — | 5 | 4 | — | — | lo > hi → done | 4 |
Notice the divergence: Both searches hit 8 at index 4 in their second iteration. But findFirst moves hi left to keep searching, while findLast moves lo right. This is the only difference, but it changes the final result from index 3 to index 4.
class Solution { public int[] searchRange(int[] nums, int target) { return new int[]{ findFirst(nums, target), findLast(nums, target) }; } // Find the LEFTMOST occurrence of target private int findFirst(int[] nums, int target) { int lo = 0, hi = nums.length - 1, result = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) { result = mid; // record this match hi = mid - 1; // but keep searching LEFT } else if (nums[mid] < target) { lo = mid + 1; } else { hi = mid - 1; } } return result; } // Find the RIGHTMOST occurrence of target private int findLast(int[] nums, int target) { int lo = 0, hi = nums.length - 1, result = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) { result = mid; // record this match lo = mid + 1; // but keep searching RIGHT } else if (nums[mid] < target) { lo = mid + 1; } else { hi = mid - 1; } } return result; } }
func searchRange(nums []int, target int) []int { return []int{findFirst(nums, target), findLast(nums, target)} } // Find the LEFTMOST occurrence of target func findFirst(nums []int, target int) int { lo, hi, result := 0, len(nums)-1, -1 for lo <= hi { mid := lo + (hi-lo)/2 if nums[mid] == target { result = mid // record this match hi = mid - 1 // but keep searching LEFT } else if nums[mid] < target { lo = mid + 1 } else { hi = mid - 1 } } return result } // Find the RIGHTMOST occurrence of target func findLast(nums []int, target int) int { lo, hi, result := 0, len(nums)-1, -1 for lo <= hi { mid := lo + (hi-lo)/2 if nums[mid] == target { result = mid // record this match lo = mid + 1 // but keep searching RIGHT } else if nums[mid] < target { lo = mid + 1 } else { hi = mid - 1 } } return result }
def search_range(nums: list[int], target: int) -> list[int]: return [find_first(nums, target), find_last(nums, target)] # Find the LEFTMOST occurrence of target def find_first(nums: list[int], target: int) -> int: lo, hi, result = 0, len(nums) - 1, -1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: result = mid # record this match hi = mid - 1 # but keep searching LEFT elif nums[mid] < target: lo = mid + 1 else: hi = mid - 1 return result # Find the RIGHTMOST occurrence of target def find_last(nums: list[int], target: int) -> int: lo, hi, result = 0, len(nums) - 1, -1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: result = mid # record this match lo = mid + 1 # but keep searching RIGHT elif nums[mid] < target: lo = mid + 1 else: hi = mid - 1 return result
impl Solution { pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> { vec![find_first(&nums, target), find_last(&nums, target)] } } // Find the LEFTMOST occurrence of target fn find_first(nums: &[i32], target: i32) -> i32 { let (mut lo, mut hi, mut result) = (0i32, nums.len() as i32 - 1, -1i32); while lo <= hi { let mid = lo + (hi - lo) / 2; if nums[mid as usize] == target { result = mid; // record this match hi = mid - 1; // but keep searching LEFT } else if nums[mid as usize] < target { lo = mid + 1; } else { hi = mid - 1; } } result } // Find the RIGHTMOST occurrence of target fn find_last(nums: &[i32], target: i32) -> i32 { let (mut lo, mut hi, mut result) = (0i32, nums.len() as i32 - 1, -1i32); while lo <= hi { let mid = lo + (hi - lo) / 2; if nums[mid as usize] == target { result = mid; // record this match lo = mid + 1; // but keep searching RIGHT } else if nums[mid as usize] < target { lo = mid + 1; } else { hi = mid - 1; } } result }
function searchRange(nums: number[], target: number): number[] { return [findFirst(nums, target), findLast(nums, target)]; } // Find the LEFTMOST occurrence of target function findFirst(nums: number[], target: number): number { let lo = 0, hi = nums.length - 1, result = -1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) { result = mid; // record this match hi = mid - 1; // but keep searching LEFT } else if (nums[mid] < target) { lo = mid + 1; } else { hi = mid - 1; } } return result; } // Find the RIGHTMOST occurrence of target function findLast(nums: number[], target: number): number { let lo = 0, hi = nums.length - 1, result = -1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) { result = mid; // record this match lo = mid + 1; // but keep searching RIGHT } else if (nums[mid] < target) { lo = mid + 1; } else { hi = mid - 1; } } return result; }
Enter a sorted array and target. Watch both binary searches run side by side, showing how they diverge when they encounter the target value.
We run binary search twice -- once for the leftmost occurrence and once for the rightmost. Each binary search takes O(log n), so the total is 2 × O(log n) = O(log n). No extra data structures are used -- just a few pointer variables, giving O(1) space.
A single pass from left to right records the first and last index where the element equals the target. If every element matches, the loop visits all n entries -- O(n). Only two index variables (first and last) are stored.
Two independent binary searches each halve the search space per iteration. findFirst continues left past matches (hi = mid - 1), while findLast continues right (lo = mid + 1). Each runs in O(log n), and 2 * O(log n) = O(log n). Only a few pointer variables are needed -- no auxiliary structures.
Same binary search template with different boundary conditions gives left and right edges. When nums[mid] == target, findFirst moves hi = mid - 1 to keep searching left, while findLast moves lo = mid + 1 to keep searching right. That single-line difference is all it takes.
Review these before coding to avoid predictable interview regressions.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.