【C++】二分查找--超详细图解（小白一看就懂！！！）
目录
一、前言
二、二分思想
✨算法引出
✨算法形成的条件
三、二分查找详解
✨写法1：左闭右闭
🥝正确的写法（正确演示）
🍍错误的写法 (错误演示)
✨写法2：左闭右开
🍎正确的写法（正确演示）
🍐错误的写法 (错误演示)
✨ 总结
四、常考面试题
💦搜索插入位置
💦在排序数组中查找元素的第一个和最后一个位置
💦x的平方根
💦有效的完全平方数
五、共勉
一、前言
二分法的思想十分容易理解，但是二分法 - 边界 - 处理问题大多数人都是记忆模板，忘记模板后处理边界就一团乱（👁:“我懂了”， ✋ :"你懂个🔨"）因为我此前也是记忆模板，所以现在想通过一边学习，一边将所学记录成博客进行复习（费曼学习法），希望以后能自己推导出边界如何处理，而不仅仅是记忆模板。欢迎一起交流学习，如有看法不一样之处也欢迎留言一起讨论！
所以本博客我主要解释了二分法的左闭右闭区间，左闭右开区间两种写法，并且每个写法都举了相应的反例，范围写错的话可能会出现的错误等…
二、二分思想
✨算法引出
故事分享🏬：
有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此，图书馆丢了 N - 1 本书。
保安怎么知道只有一本书📖没有登记出借，万一全部都没有登记呢？
✨算法形成的条件
这个故事其实说出了二分查找需要的条件 ！！!
- 用于查找的内容逻辑上来说是需要有序的
- 查找的数量只能是一个，而不是多个
比如在一个 有序的数组 并且 无重复元素 的数组中，例如[1, 2, 3, 4, 5, 6]，需要查找3的位置就可以使用二分查找。
因为查找的区间是不断迭代的，所以确定查找的范围十分重要，主要就是左右区间的开和闭的问题，开闭不一样，对应的迭代方式也不一样，有以下两种方式：
-
左闭右闭: [left, right]
-
左闭右开: [left, right)
三、二分查找详解
首先我们通过一道题，来深入了解 二分查找 的细节
题目：二分查找
链接：704. 二分查找 - 力扣（LeetCode）
题目分析：
二分法的思想很简单，因为整个数组是有序的，数组默认是递增的。
- 首先选择数组中间的数字和需要查找的目标值比较
- 如果相等最好，就可以直接返回答案了
- 如果不相等
1. 如果中间的数字大于目标值，则中间数字向右的所有数字都大于目标值，全部排除
2. 如果中间的数字小于目标值，则中间数字向左的所有数字都小于目标值，全部排除
二分法就是按照这种方式进行快速排除查找的
tips:
不用去纠结数组的长度是奇数或者偶数的时候，怎么取长度的一半，以下说明，可以跳过。
⚡当数组的长度为奇数的时候⚡
是奇数的情况很简单，指向中间的数字很容易理解，如果需要查找的数字为29
因为29大于中间的数字大于11，所以左边的所有数字全部排除
⚡ 当数组的长度为偶数的时候⚡
这个时候 中间的数字 和 两边的数字 数量就不一样了（刚开始学习二分法的时候我经常纠结这个问题，和另外一个 长度除2得到的是最中间的数吗的问题，我相信不止我一个人纠结过……但其实这是同一个问题，每次长度除2，如果长度为奇数，得到的中间的数字两边数字数量相同，如果长度为偶数就为上图中间的数字两边的相差为 1）
但是千万不要一直纠结中间的数字两边的数字数量不一样这个问题，因为：
- 两边数量不一样是一定会出现的情况
- 但是这种情况并不影响我们对中间数字和目标数字大小关系的判断
- 只要中间数字大于目标数字，就排除右边的
- 只要中间数字小于目标数字，就排除左边的
所以数组长度是偶数还是奇数这个真的不重要，不影响怎么排除的问题，无非是多排除一个数字或者少排除一个数字
真正影响的是中间那个数字到底该不该加入下一次的查找中，也就是边界问题
✨写法1：左闭右闭
二分法最重要的两个点：
- while循环中 left 和 right 的关系，到底是 left target)，代表middle向右所有的数字大于target
- if (nums[middle]
- 既不大于也不小于就是找到了相等的值
nums[middle] = 13
见下图：
-
循环条件为 while (left target)， right = middle，因为当前的 nums[middle] 是大于 target 的，不符合条件,不能取到 middle，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 middle。
代码如下：
class Solution { public: int search(vector& nums, int target) { int left = 0; int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right) while (left > 1); // >>右移运算符 向右移动一位相当于除2 if (nums[mid] > target) { right = mid; // target 在左区间，在[left, middle)中 } else if (nums[mid]图列解析如下：
第一步是初始化 left 和 right 的值，然后计算 middle 的值
- left = 0, right = size
- 循环条件while (left 因为是左闭右开区间，所以数组定义如下：
- 计算 middle 的值
- 比较 nums[middle] 和 target 的大小：因为 nums[middle] = 22 > target = 3
- 所以 right = middle
- 符合循环的条件，接着计算 middle 的值
- 比较 nums[middle] 和 target 的大小：因为 nums[middle] = 9 > target = 3
- 所以 right = middle
- 符合循环的条件，继续计算 middle 的值
- 比较 nums[middle] 和 target 的大小关系：因为nums[middle] = 0
- 所以 left = middle + 1
- 符合循环条件，接着计算 middle 的值
- 比较 nums[middle] 和 target 的关系：nums[middle] = 3 == target = 3
- 成功找到 target
🍐错误的写法(错误演示)
对应第二种正确的写法，照样把循环条件修改，看会发生什么事
正确的写法中条件为：
- 查找原区间 [left, right)
- 循环条件为 while (left 修改后题目对应的条件：
-
查找区间不变，仍然是 [left, right)
-
循环条件修改为：while (left 1); // >>右移运算符 向右移动一位相当于除2 if (nums[mid] > target) { right = mid; // target 在左区间，在[left, middle)中 } else if (nums[mid]
图例详解：以下是演示全过程：
- 同样，开始初始化一个数组
- 先计算 middle 的值
- 判断 nums[middle] 和 target 的大小关系：nums[middle] = 22
- left = middle + 1 （其实这里nums[left] 已经等于27，26不可能找到，接下去就看算法是否能够知道数组中不存在26并且返回-1 了）
- 符合循环条件，计算 middle 的值
- 判断 nums[middle] 和 target 的大小关系：nums[middle] = 57 > target = 26
- right = middle
- 符合循环条件，计算 middle 的值
- 先计算 middle 的值
- 同样，开始初始化一个数组
-
- 符合循环条件，接着计算 middle 的值
- 符合循环的条件，继续计算 middle 的值
- 符合循环的条件，接着计算 middle 的值
- 计算 middle 的值
-
-
