Problem
Given a sorted array, find the first and last position of target. Return [-1, -1] if not found. Must run in O(log n).
Example
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]Solution
Two binary searches. First finds leftmost occurrence; second finds rightmost.
def search_range(nums, target):
def find(left_bias):
l, r, idx = 0, len(nums) - 1, -1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
idx = mid
if left_bias: r = mid - 1
else: l = mid + 1
elif nums[mid] < target: l = mid + 1
else: r = mid - 1
return idx
return [find(True), find(False)]function searchRange(nums, target) {
function find(leftBias) {
let l = 0, r = nums.length - 1, idx = -1;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (nums[mid] === target) {
idx = mid;
if (leftBias) r = mid - 1;
else l = mid + 1;
} else if (nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return idx;
}
return [find(true), find(false)];
}int find(vector<int>& nums, int target, bool leftBias) {
int l = 0, r = nums.size() - 1, idx = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
idx = mid;
if (leftBias) r = mid - 1;
else l = mid + 1;
} else if (nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return idx;
}
vector<int> searchRange(vector<int>& nums, int target) {
return {find(nums, target, true), find(nums, target, false)};
}public int[] searchRange(int[] nums, int target) {
return new int[]{find(nums, target, true), find(nums, target, false)};
}
private int find(int[] nums, int target, boolean leftBias) {
int l = 0, r = nums.length - 1, idx = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
idx = mid;
if (leftBias) r = mid - 1;
else l = mid + 1;
} else if (nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return idx;
}Complexity
- Time: O(log n)
- Space: O(1)
Explanation
On a match, instead of returning, keep searching left (for first) or right (for last). Saves the index along the way.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?