📚 Table of Contents
📋 Problem Statement
Array is sorted in non-decreasing order.
Return the smallest and largest indices where nums[i] == target.
Examples
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6Output: [-1,-1]
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9numsis sorted
🎯 Real-World Analogy
Finding First and Last Book on a Shelf
Books are sorted alphabetically. You want the first and last position of a title. One search finds the left boundary, another finds the right boundary.
Instead of scanning every book, jump to the middle repeatedly. Direction depends on whether middle is before or after boundary condition.
💡 Key Insights
- Use two binary searches: one for lower bound, one for upper bound.
- Left boundary: first index where
nums[i] >= target. - Right boundary: first index where
nums[i] > target, then subtract 1. - If left index is out of range or value != target, target does not exist.
- This meets required O(log N) runtime.
💻 Solution Approaches
Approach 1: Linear Scan
Time: O(N) | Space: O(1)
Simple but violates logarithmic follow-up requirement.
Approach 2: Two Binary Searches (Recommended)
Time: O(log N) | Space: O(1)
Find the target interval boundaries directly.
Python Implementation
from typing import List
def search_range(nums: List[int], target: int) -> List[int]:
def first_ge(x: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < x:
left = mid + 1
else:
right = mid
return left
left = first_ge(target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = first_ge(target + 1) - 1
return [left, right]
JavaScript Implementation
function searchRange(nums, target) {
function firstGE(x) {
let left = 0;
let right = nums.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < x) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
const left = firstGE(target);
if (left === nums.length || nums[left] !== target) {
return [-1, -1];
}
const right = firstGE(target + 1) - 1;
return [left, right];
}
🔍 Step-by-Step Walkthrough
Trace nums=[5,7,7,8,8,10], target=8:
first_ge(8) returns index 3 (first 8).
first_ge(9) returns index 5 (value 10).
Right boundary = 5 - 1 = 4. Answer = [3,4].
⚡ Complexity Analysis
Time Complexity: O(log N)
- Each binary search halves interval each step.
- Two searches: O(log N) + O(log N) = O(log N).
Space Complexity: O(1)
- Only pointer variables are used.
- No extra arrays or recursion needed.
🔧 Edge Cases
- Empty array ->
[-1,-1] - Target absent
- All values equal to target
- Target appears once
- Target at beginning or end
🧪 Test Cases
Python
def test_search_range():
assert search_range([5,7,7,8,8,10], 8) == [3, 4]
assert search_range([5,7,7,8,8,10], 6) == [-1, -1]
assert search_range([], 1) == [-1, -1]
assert search_range([2,2,2,2], 2) == [0, 3]
assert search_range([1,3,5], 3) == [1, 1]
print("✅ all tests passed")
JavaScript
function testSearchRange() {
console.assert(JSON.stringify(searchRange([5,7,7,8,8,10], 8)) === JSON.stringify([3,4]), "test 1");
console.assert(JSON.stringify(searchRange([5,7,7,8,8,10], 6)) === JSON.stringify([-1,-1]), "test 2");
console.assert(JSON.stringify(searchRange([], 1)) === JSON.stringify([-1,-1]), "test 3");
console.log("✅ all tests passed");
}
💼 Interview Tips
- Explain why one binary search is not enough for full range.
- Use half-open interval [left, right) to avoid off-by-one bugs.
- Define helper boundary function once and reuse it.
- Always validate left boundary before computing right.
- Mention follow-up target: O(log N) runtime.
🎓 Key Takeaways
- Boundary-focused binary search is the core pattern here.
- First-true style helper avoids duplicated bug-prone logic.
- Two logarithmic passes beat all linear scans for sorted arrays.