初识算法 · 二分查找(2)
目录
前言：
本文的目标和之前的算法文章不太一样，像最开始的双指针算法，到滑动窗口算法，都是从题目中解析该算法原理，但是通过第一次的二分查找原理的算法，显然从题目中学习该算法的效果并不是很好，所以在本文中，博主将着重介绍二分查找的原理，对于最简单的朴素二分模板，我们肯定是不用介绍的，因为太简单了，更多信息，我们直接通过题目引出。
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
进入正题。
题目解析
题目给出的信息是非递减顺序排序的整数数组，既然是非递减的，也就是代表，数组是升序，或者是不变的，也就是值是这样变化的：
那么对于暴力解法来说，是非常简单的，一个for循环就可以直接遍历了，但是同样，没有利用到数组非递减的特点，对于的效率可以说是42亿次和32次的区间，但是我们这道题可以使用朴素的二分查找吗？
根据题目要求，我们需要查找两个端点，一个是target起始的端点，一个是target结束的端点，那么如果用朴素的二分模板，我们只能找到一个值不说，如果mid直接精准命中target区间的任意一个值，我们应该如何判断该值是不是我们要求的目标区间呢？
由前文，我们知道，使用二分区间的前提是该数组（区间）具有二段性。
所以我们现在的问题是，如何从这段区间里面寻找二段性呢？
对于这段区间，因为target的值是3，所以我们可以区间划分为<target 和 >= target的区间，此时数组具有了二段性，有了二段性，我们查找题目要求的那个值，就可以使用二分了。
那么，进入到查找端点部分。
查找左端点
如果mid < target，那么mid落在的区间一定是[left,target]的区间，此时一定不是答案，因为该区间就存在我们需要的答案，那么，如果mid >= target的话，此时mid落在的区间是[target,nums.size() - 1]这个区间，那么是可能命中正确答案的。所以，如果移动right的话，一定是不能right = mid - 1的，说不定就错过了正确答案，所以得出：
那么查找左端点的大致情况就确定了，但是为什么这样操作可以确定左端点呢？因为right最后的移动是等于mid的，而mid是慢慢减少，直至减到了[target,nums.size() - 1]的左端点，也就是我们成功找到了左端点。
但是如果这么简单，肯定就不符合二分查找恶心的特点了，所以我们要处理细节问题：
1. 循环条件的判断 2. 求中点的操作
循环条件的判断
如果是left <= right的话，那么势必是会导致死循环的，因为left = mid + 1，right = mid，也就是说如果结束条件是left > right的话。
当最后走的是第一种情况的话，x < target的情况，left = mid + 1，也就是最后left = right，此时继续走，left最后走到了right + 1的位置，那么是满足条件的，但是但是，如果走的是第二种情况，也就是right = mid，那么mid的位置是left，此时left mid right都是一起，那么问题就来了，right会一直走x >= t的情况，也就是right = mid是永恒的情况，此时while的判断条件是left <= right，所以就会导致死循环的情况。
所以对于死循环的情况我们就分析完成了，那么现在进入求重点操作的部分。
求中点的操作
对于二分查找来说，因为涉及到left + right，两个整型的相加，所以可能会发生溢出，我们都是采用的left + (right - left) / 2的情况来防溢出。
那么问题来了，在朴素二分模板的情况下，left + (right - left) / 2是否 + 1都是无所谓的，但是在查找左右端点这里的求中点操作却是尤为重要了：
我们就拿极端情况举例子，如果我们使用left + (right - left + 1) / 2的操作，那么mid就等于right，此时如果是情况1，left = mid + 1，那么就会到right + 1部分，满足条件，跳出循环，如果是情况2，也就是x >= target，此时mid = right，就会造成死循环。
那么如果是left + (right - left) / 2，mid的首先落点是left，情况1，left = mid + 1，left到了right的位置，此时满足结束条件，如果是情况2，right = mid，此时left 和 righ是一样的，此时满足结束条件。
所以在查找左端点的部分，中点操作应该是int mid = left + (right - left) / 2。
查找右端点
有了查找左端点的基础，右端点是十分类似的，首先，我们分析left和right是如何变化的。
数组因为二段性，我们已经将其分为了[left,target] [target + 1,right]的部分，那么mid如果落点是在第一个区间的位置，那么x <= target，所以有可能是命中我们需要的答案的，所以left = mid，right的情况肯定就是right = mid - 1了。
主要的细节还是分析循环条件的判断和中点的操作。但是循环条件相信我不说，同学也应该知道是left < right，因为left是一直靠，最后靠到target，right是一直往左靠，最后到target的部分，最后left right是一样，我们判断是否满足条件只需要将target和nums[left]进行简单的比较即可。
求中点的操作
对于求中点，我们依旧拿极端情况举例：
如果我们使用的是left + (right - left) / 2的操作，那么mid的落点是在left的位置，那么如果是小于target的话，就会left = 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 begin = 0, end = 0;
//查找左端点
int left = 0, right = nums.size() - 1,mid = 0;
while(left < right)
{
mid = left + (right - left) / 2;
if(nums[mid] < target) left = mid + 1;
else right = mid;
}
if(nums[left] != target) return { -1, -1};
else begin = left;
//查找右端点
right = nums.size() - 1;
while(left < right)
{
mid = left + (right - left + 1) / 2;
if(nums[mid] <= target) left = mid;
else right = mid - 1;
}
end = right;
return {begin, end};
}
};我们需要找到左右端点即可，查找右端点时候，left = 0不是必要的，因为left肯定是在target的左区间部分。并且，题目给了空数组，所以我们应该判断一下，空数组的情况，查找完左端点，判断即可。
到此，二分查找的基本原理才算是讲解完毕。
浅看一下时间复杂度吧，二分查找确实快啊。
感谢阅读！
原文地址：https://blog.csdn.net/2301_79697943/article/details/142992921
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！