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] <= 109
nums
is a non-decreasing array.-109 <= target <= 109
Solution: Binary Search
Use lower_bound to find first
Use upper_bound to find last + 1
Time complexity: O(logn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { auto it = lower_bound(begin(nums), end(nums), target); int l = (it == end(nums) || *it != target) ? -1 : it - begin(nums); auto it2 = upper_bound(begin(nums), end(nums), target); int r = (it2 == begin(nums) || *prev(it2) != target) ? -1 : prev(it2) - begin(nums); return {l, r}; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment