力扣 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;
}
};