二分查找
开源链接:【 教程地址 】【电子网站】
1.1 二分查找算法思路
前提:有序的数组(升序或者降序排列)
确定左右端点后(left和right),每次将中间元素与目标元素相比较:
如果相同则找到了目标元素,如果中间元素比目标元素小,则在中间元素的右边去查找;如果中间元素比目标元素大,则在中间元素的左边去查找,这样每次就减少了一半的查找。
1.2 代码实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size();
while (l < r) {
int mid = l + (r - l) / 2;
//写成mid=(r-l)/2的方式容易造成溢出。
if (nums[mid] > target) r = mid;
else if (nums[mid] < target) l = mid + 1;
else return mid;
}
return -1;
}
};
二分查找细节知识
1.区间开闭问题
左闭右闭区间:left=0,right=len(nums)-1。对应数组下标,这样每个数值就都能取到。
左臂右开区间:初始化left=0,right=len(nums)。会使得问题可能变得复杂,考虑别的情况更多。
所以更为推荐使用左闭右开区间。
2.mid取值问题
mid公式有两个是由数组个数的奇偶决定的,当为奇数个元素,mid=(l+r)//2和(l+r+1)//2都可以使用。如果为偶数个,使用前者获得靠左边元素的下标位置,使用后者获得中间靠右边的下标位置。但其实靠左或者靠右最终都能够找到目标元素。但是如果取值越靠近中间位置平均意义上效果做好。并且为了防止整数溢出,将上面两个公式修改为·:
mid=left+(right-left)//2;
mid=left+(right-left+1)//2;
3.出界条件的判断
- 如果判断语句为left<=right,并且查找的元素不在有序数组中,则while的出界条件是left>right,也就是left==right+1,则终止循环。
- 如果判断语句为left<right,并且查找的元素不在有序数组中,则while语句的出界条件是left==right,写成区间形式就是[right,right],此区间不为空,因为待查找区间还有一个元素存在,我们并不能确定查找的元素不在这个区间中,此时终止循环返回就是错误的,因此我们需要在出界之后增加一层判断,判断剩余的那个元素是否等于目标元素,如果相等就返回left,不是的话返回-1。
left<right
4.搜索范围的选择
两个思路:
- 在循环体内找到元素后直接返回结果。
- 在循环体内排除目标元素一定不存在区间。(找边界问题。)
Leetcode之旅~:
【2】0035.搜索插入位置
代码思路:直接法进行二分法查找,然后在出界条件添加一个判断,如果没找到,那就把目标元素补在数组后面。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left =0;
int right=nums.size()-1;
int mid=0;
while(left<=right){
mid = left + (right-left) / 2;
if (nums[mid]==target){
return mid;
}else if(nums[mid]<target){
left=mid+1;
}else{
right = mid-1;
}
}
if(nums[mid]<target){
return mid+1;
}else{
return mid;
}
}
};
【3】0374
代码实现:
思路:其实还是使用二分法进行查找,只不过这里的判断条件稍微修改一下,然后的话是使用了调用guess函数来取出mid变量,使得时间更加的快。
class Solution {
public:
int guessNumber(int n) {
int left = 1, right = n;
while(left <= right) {
int mid = left + (right - left) / 2;
int flag = guess(mid);
if(flag == 0)
return mid;
else if(flag == -1)
right = mid - 1;
else if(flag == 1)
left = mid + 1;
}
return -1;
}
};
溜了溜了,回不去宿舍了。。。
参考资料:
[1] 【教程地址 】[电子网站]
[2]Hello 算法教程
https://leetcode.cn/problems/guess-number-higher-or-lower/solutions/826884/c-er-fen-cha-zhao-by-qiank-tcj0/
感谢:DataWhale社区