Welcome to Subscribe On Youtube
34. Find First and Last Position of Element in Sorted Array
Description
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] <= 109numsis a non-decreasing array.-109 <= target <= 109
Solutions
Solution 1: Binary Search
We can perform binary search twice to find the left and right boundaries respectively.
The time complexity is $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.
Below are two general templates for binary search:
Template 1:
boolean check(int x) {
}
int search(int left, int right) {
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
Template 2:
boolean check(int x) {
}
int search(int left, int right) {
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
When doing binary search problems, you can follow the following routine:
- Write out the loop condition $left < right$;
- Inside the loop, you might as well write $mid = \lfloor \frac{left + right}{2} \rfloor$ first;
- According to the specific problem, implement the $check()$ function (sometimes the logic is very simple, you can not define $check$), think about whether to use $right = mid$ (Template $1$) or $left = mid$ (Template $2$);
- If $right = mid$, then write the else statement $left = mid + 1$, and there is no need to change the calculation of $mid$, that is, keep $mid = \lfloor \frac{left + right}{2} \rfloor$;
- If $left = mid$, then write the else statement $right = mid - 1$, and add +1 when calculating $mid$, that is, $mid = \lfloor \frac{left + right + 1}{2} \rfloor$;
- When the loop ends, $left$ equals $right$.
Note that the advantage of these two templates is that they always keep the answer within the binary search interval, and the value corresponding to the end condition of the binary search is exactly at the position of the answer. For the case that may have no solution, just check whether the $left$ or $right$ after the binary search ends satisfies the problem.
-
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin(); int r = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin(); if (l == r) return {-1, -1}; return {l, r - 1}; } }; -
''' >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 2) 3 >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 2+1) 6 >>> bisect.bisect_right([1,1,1,2,2,2,7,7,7], 2) 6 >>> bisect.bisect_right([1,1,1,2,2,2,7,7,7], 2+1) 6 >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 0) 0 >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 1) 0 # below, even single value for 2, after +1 the index will be different >>> bisect.bisect_left([1,2,3,4,5], 2) 1 >>> bisect.bisect_left([1,2,3,4,5], 2+1) 2 ''' import bisect class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: l = bisect_left(nums, target) r = bisect_left(nums, target + 1) return [-1, -1] if l == r else [l, r - 1] ############ class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: def findRange(to_left): l, r = 0, len(nums) - 1 m = 0 while l <= r: m = l + (r - l) // 2 if nums[m] < target: l = m + 1 elif nums[m] > target: r = m - 1 elif to_left and m > 0 and nums[m - 1] == nums[m]: # so now nums[m] == target, but maybe not the leftmost or rightmost r = m - 1 elif not to_left and m + 1 < len(nums) and nums[m + 1] == nums[m]: # so now nums[m] == target, but maybe not the leftmost or rightmost l = m + 1 else: return m if m < len(nums) and nums[m] == target: # 1. cover not-found, # or 2. cover input=[3] and target=3, first and last both 0, return [0,0] return m else: return -1 return [findRange(True), findRange(False)] -
func searchRange(nums []int, target int) []int { l := sort.SearchInts(nums, target) r := sort.SearchInts(nums, target+1) if l == r { return []int{-1, -1} } return []int{l, r - 1} } -
function searchRange(nums: number[], target: number): number[] { const search = (x: number): number => { let [left, right] = [0, nums.length]; while (left < right) { const mid = (left + right) >> 1; if (nums[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; }; const l = search(target); const r = search(target + 1); return l === r ? [-1, -1] : [l, r - 1]; } -
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var searchRange = function (nums, target) { function search(x) { let left = 0, right = nums.length; while (left < right) { const mid = (left + right) >> 1; if (nums[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; } const l = search(target); const r = search(target + 1); return l == r ? [-1, -1] : [l, r - 1]; }; -
impl Solution { pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> { let n = nums.len(); let search = |x| { let mut left = 0; let mut right = n; while left < right { let mid = left + (right - left) / 2; if nums[mid] < x { left = mid + 1; } else { right = mid; } } left }; let l = search(target); let r = search(target + 1); if l == r { return vec![-1, -1]; } vec![l as i32, (r - 1) as i32] } } -
class Solution { /** * @param integer[] $nums * @param integer $target * @return integer[] */ function searchRange($nums, $target) { $min = -1; $max = -1; foreach ($nums as $key => $value) { if ($value == $target) { if ($min == -1) { $min = $key; } if ($key > $max) { $max = $key; } } } return [$min, $max]; } } -
public class Solution { public int[] SearchRange(int[] nums, int target) { int l = Search(nums, target); int r = Search(nums, target + 1); return l == r ? new int[] {-1, -1} : new int[] {l, r - 1}; } private int Search(int[] nums, int x) { int left = 0, right = nums.Length; while (left < right) { int mid = (left + right) >>> 1; if (nums[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; } }