1. LeetCode 34. Find First and Last Position of Element in Sorted Array
- class Solution {
- public:
- vector<int> searchRange(vector<int>& nums, int target) {
- vector<int> ans = {-1, -1};
- if(nums.size() == 0) return ans;
- int l=0, r=nums.size();
- // 找到最左边的元素
- while(l <r){
- int mid = l + (r - l) /2;
- if(nums[mid]>= target)
- r = mid;
- else
- l = mid + 1;
- }
- if(l==nums.size() || nums[l] != target)
- return ans;
- ans[0] = l;
- // 找最右边的元素
- r = nums.size();
- while(l <r){
- int mid = l + (r - l) /2;
- if(nums[mid]> target)
- r = mid;
- else
- l = mid+1;
- // 错误写法
- //if(nums[mid]> target) r = mid - 1;
- //else l = mid; // 当 l==mid, r 保持不变时会死循环,
- }
- ans[1] = l-1;
- return ans;
- }
- };
来源: http://www.bubuko.com/infodetail-3119090.html