欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

力扣 704. 二分查找 C++

程序员文章站 2024-01-04 15:54:40
...

解题思路与方法:left对应查找的起始位置,right对应查找的最后位置,mid对应中间位置

比较mid处的值和target.的值,如果相等则返回,大于则让right改到mid-1处,小于则left改为mid+1处

总结:简单的也是最经典的二分查找,要注意的地方主要是:1、求mid的值时应该采取left+(right-left),不能采取(right+left)/2,以防止数据溢出;2、大于时,right应改到mid-1处,小于时left应改到mid+1处,以减少运行时间

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while(left<=right)
        {
            int mid=left+(right-left)/2;//不用(right+left)/2的原因防止溢出
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]<target){
                left=mid+1;//左加一
            }
            else
            {
                right=mid-1;//右减一
            }
        }
        return -1;
    }
};

上一篇:

下一篇: