Given an array of integers nums
sorted in ascending order, find the starting and ending position of a given target
value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1]
.
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]
Solution: Binary Search
Basically this problem asks you to implement lower_bound and upper_bound using binary search.
Time complexity: O(logn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
// Author: Huahua class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { return {firstPos(nums, target), lastPos(nums, target)}; } private: int firstPos(const vector<int>& nums, int target) { int l = 0; int r = nums.size(); while (l < r) { int m = l + (r - l) / 2; if (nums[m] >= target) { r = m; } else { l = m + 1; } } if (l == nums.size() || nums[l] != target) return -1; return l; } int lastPos(const vector<int>& nums, int target) { int l = 0; int r = nums.size(); while (l < r) { int m = l + (r - l) / 2; if (nums[m] > target) { r = m; } else { l = m + 1; } } // l points to the first element this is greater than target. --l; if (l < 0 || nums[l] != target) return -1; return l; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment