admin管理员组文章数量:1446753
【二分查找】二分查找详解 && 二分模板
704. 二分查找
704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例 2:
代码语言：javascript代码运行次数：0运行复制输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
解题思路
算法思路很简单，因为在数学概率领域已经得出了结论：一段区间内（不一定是有序，如果符合二分规律的话也是可以的），在保证正确性的前提下进行二分，此时寻找到目标元素的次数普遍最少，也就是说比起三等分、四等分等划分方式，二分是一种最优秀的解法！
那我们就可以使用双指针来进行二分的操作！
算法步骤如下：
- 定义
left和right指针分别指向数组的左右边界。 - 找到待查找区间的中间点
mid，找到之后分三种情况讨论：- 如果
nums[mid] == target，说明找到目标元素，则直接返回结果。 - 如果
nums[mid] > target，说明在[left, mid]区间内该目标元素是不会存在的，则直接让left = mid + 1，舍弃[left, mid]区间！ - 如果
nums[mid] < target，说明在[mid, right]区间内该目标元素是不会存在的，则直接让right = mid - 1，舍弃[mid, right]区间！
- 如果
- 重复上述操作，直到
left超过了right，即当left > right的时候就结束循环。
细节处理
① 终止循环条件
为什么终止循环条件不包括 left == right 呢❓❓❓
此时我们就得先了解我们的二分算法是如何执行的！当左右指针 left 和 right 在移动的时候，还需要有一个中间指针 mid 来判断是否找到 target，假设此时 left == right，如果我们继续循环的话，那么 mid 通过左右指针平分后得到的下标，其实就是指向 left/right，此时再去判断该处元素是否就是 target，如果不是的话下一次循环 left 肯定会大于 right 了，也就是说明找不到 target 了。
而如果我们在 left == right 就终止循环的话，那么就不会有 mid 去判断该处的元素是否为 target 了，相当于可能错过了 target！
② 解决 mid 的溢出问题
一般我们习惯直接通过 (left + right) / 2 来获得 mid，此时其实是有溢出问题的，如果 left 或者 right 非常的大，累加完就是一个很大的数，有可能就超出范围了！
如果说我们用其它更大范围的整型来存储 left 和 right 也行，但是我们有更牛的做法！
直接通过 left + (right - left) / 2 来获取 mid 就不会溢出了，为什么这样子不会溢出❓❓❓
因为这里使用了减法来避免这个问题，单独一个
left其实是不会溢出的，而right - left更不会溢出，此时让(right - left) / 2，其实就是它们的差值被平分了，那么left加上这个差值平分值，其实就直接等于mid了，而因为mid本身也是不可能会溢出的，其是通过left加上一个不大的数来得到的，并不会造成说溢出的情况！
另外用 left + (right - left + 1) / 2 对于这道题同样也是可以的。
拿两个比较极端的例子，就是 left == right 和 left + 1 == right，前者算出来整个表达式是 left + 0.5 最后得到的还是 left，而后者算出来整个表达式是 left + 1，也就是说当前这个表达式有可能会出现在不同的位置，但是对于这道题是没问题的，因为此时如果是 left + 1 的情况，并且不等于目标元素，那么 left 或者 right 还需要再走一步，最后肯定会重叠，然后返回！
但是这两个表达式对后面的 34. 在排序数组中查找元素的第一个和最后一个位置 这道题来说情况就有点不一样了，总之，这里是两者都可用！
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
int search(vector<int>& nums, int target)
{
int left = 0, right = nums.size() - 1;
while(left <= right)
{
// 先找到区间的中间元素
int mid = left + (right - left) / 2;
if(nums[mid] < target)
left = mid + 1;
else if(target < nums[mid])
right = mid - 1;
else
return mid;
}
// 如果程序走到这里，说明没有找到目标值，返回 -1
return -1;
}
};本文标签： 二分查找二分查找详解 ampamp 二分模板
版权声明：本文标题：【二分查找】二分查找详解 && 二分模板 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/biancheng/1748228925a2829454.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论