有趣的地方

有趣的地方

【C++】二分查找算法(模板)

重点

只需要记住两点:
1.left = right 时,一定就是最终结果(包括找不到目标值),无需再次判断,如果判断就会死循环
2.求中点如果是求左端点 mid = left + (right - left)/2
如果是求右端点 mid = left + (right - left + 1)/2
简称(右加一)
请添加图片描述
请添加图片描述

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
       
       if(nums.size() == 0) return {-1, -1};
       int left = 0;
       int right = nums.size()-1;
       //寻找左点端
       int begin = 0;
       while(left < right)
       {
        int mid = left + (right - left)/2;
        if(nums[mid] < target) left = mid+1;
        else if(nums[mid] >= target) right = mid;
       }
      if(nums[left] != target) return {-1, -1};
        else begin = left;
       
       //寻找右端点
       left = 0;
       right = nums.size()-1;
       while(left < right)
       {
        int mid = left + (right-left+1)/2;
        if(nums[mid]<=target) left = mid;
        else right = mid-1; 
       }
       return {begin,right};
    }
};

发表评论:

Powered By Z-BlogPHP 1.7.3

© 2018-2020 有趣的地方 粤ICP备18140861号-1 网站地图