First and Last Index of a Sorted Value
Problem
In a sorted array, return the first and last indices of target as a pair, or [-1, -1] if it does not appear.
Input
nums = [5,7,7,8,8,10], target = 8Output
[3, 4]Two binary searches: lower-bound finds the first ≥ target; upper-bound finds the first > target. The last index is upper − 1.
def search_range(nums, target):
def bound(strict):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target or (strict and nums[mid] == target):
lo = mid + 1
else:
hi = mid
return lo
first = bound(False)
last = bound(True) - 1
if first <= last: return [first, last]
return [-1, -1]function searchRange(nums, target) {
function bound(strict) {
let lo = 0, hi = nums.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < target || (strict && nums[mid] === target)) lo = mid + 1;
else hi = mid;
}
return lo;
}
const first = bound(false);
const last = bound(true) - 1;
return first <= last ? [first, last] : [-1, -1];
}class Solution {
public int[] searchRange(int[] nums, int target) {
int first = bound(nums, target, false);
int last = bound(nums, target, true) - 1;
return first <= last ? new int[]{first, last} : new int[]{-1, -1};
}
private int bound(int[] nums, int target, boolean strict) {
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] < target || (strict && nums[mid] == target)) lo = mid + 1;
else hi = mid;
}
return lo;
}
}vector<int> searchRange(vector<int>& nums, int target) {
auto bound = [&](bool strict) {
int lo = 0, hi = (int) nums.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] < target || (strict && nums[mid] == target)) lo = mid + 1;
else hi = mid;
}
return lo;
};
int first = bound(false), last = bound(true) - 1;
return first <= last ? vector<int>{first, last} : vector<int>{-1, -1};
}