目录
1. 二分算法是什么？
2. 朴素二分
朴素二分的模板
3. 查找左边界二分
查找左边界二分的模板
4. 查找右边界二分
查找右边界二分的模板
5. 小结
6. 应用实例
1. X的平方根
2. 搜索插入位置
3. 山脉数组的峰顶索引
4. 寻找峰值
5. 寻找旋转排序数组中的最小值
6. 点名
简单来说，"二分"指的是将查找的区间一分为二，通过比较目标值与中间元素的大小关系，确定目标值可能在哪一半区间内，从而缩小查找范围。这个过程不断重复，每次都将当前区间二分，直到找到目标值或确定目标值不存在为止。这种分而治之的策略使得二分查找算法具有较高的效率，时间复杂度为O(log n)。
大致图解如下
即通过二段性，在每次判断过后可以一次性减少将近一半的数据，然后通过不断的挪移左右区间来筛选出最后的结果。
在这里我们通过一个例题来讲解：704. 二分查找 - 力扣（LeetCode）
题目描述如下
看到这个题目之后我们首先想到的一定是暴力解法：
从头遍历数组，将每个值与target比较，若遍历到结束还没有找到就返回-1， 否则返回对应下标
我们稍加分析可以发现这个解法的时间复杂度是O(N)，我们没有使用到数组升序的性质，我们可以在暴力解法上稍作优化，修改为二分查找：
定义左右指针left, right，然后计算中间值，将其与target比较，由于升序，若中间值小于target，则表明此时中间值及其左边的值均小于target，此时target理应存在于[mid+1, right]，因此令left = mid+1； 若中间值大于target，则表明此时中间值及其右边的值均小于target， 此时target理应存在于[left, mid-1]，因此令right = mid-1；相等时返回mid下标即可。
大致图解如下
代码如下
在这里有两个值得关注的细节，其中一个是while循环的结束条件，在这里由于left与right的变化始终是在mid的基础上+1或-1，因此在left==right的时候，会因为边界的变化而导致退出循环，因此退出的条件是left > right；另一个是mid的计算方式，在计算mid时我们有两种计算方式：一种是mid = left + (right - left) / 2，另一种是mid = left + (right - left + 1) / 2，这两种方式在具体的过程中体现为
可以看到两种计算方式只有在数据个数为偶数时才会发生变化，意为分别取到中左与中右的下标。
模板如下
讲解 查找左边界二分与查找右边界二分 时，我们使用例题：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
题目描述如下
简单分析后我们可以得出一个简单的暴力解法：
从头到尾遍历一遍数组，使用begin与end分别标识一下这个元素第一次出现与最后一次出现的位置并返回，否则返回{-1, -1}
我们可以在此基础上优化：
定义左右指针left, right与标识符begin, end，寻找元素的第一次出现位置本质就是查找左边界，而寻找元素的最后一次出现位置本质就是查找右边界。
在查找左边界时，计算出中间值并将其与target比较，如果中间值<target，说明左边界理应存在于[mid+1, right]区间中，因此left = mid+1，如果中间值>=target，说明左边界理应存在于[left, mid]区间中，因此right = mid；
查找左边界图解如下
在查找左边界时，我们同样需要关注两个细节：
1. while 循环的退出条件：在上面的查找过程中我们可以发现查找到最后left与right可能会指向同一个位置，此时如果使用while (left <= right)则会陷入死循环，因此退出条件为left>=right
2. 中点下标的选取方式：在朴素二分那里我们知道选取方式有两种，在这里我们选取左边中点，其图解如下
可以看到，如果选取右边的中点可能会导致死循环或下标进入不合理区间
因此我们可以得到查找左边界代码如下
模版如下
在查找右边界时，计算出中间值并将其与target比较，如果中间值>target，说明右边界理应存在于[left, mid-1]区间中，因此right = mid-1，如果中间值<=target，说明右边界理应存在于[mid, right]区间中，因此left = mid；
查找右边界图解如下
与查找左边界类似，我们同样需要关注两个细节
1. while 循环的退出条件：同上，在查找过程中我们可以发现查找到最后left与right可能会指向同一个位置，此时如果使用while (left <= right)则会陷入死循环，因此退出条件为left>=right
2. 中点下标的选取方式：在朴素二分那里我们知道选取方式有两种，在这里我们选取右边中点，其图解如下
可以看到，如果选取左边的中点可能会导致死循环或下标进入不合理区间
因此我们可以得到查找右边界代码如下
模板如下
解决问题完整代码如下
二分查找算法的细节比较多，但是当我们真正把它分析透彻后，我们仅需要结合理解背住模板，即
对于分类讨论的代码，我们具体情景具体实现
对于中点的选取，我们为了快捷可以记：分类讨论出现 -1 的时候上面就 +1
即
题目链接：69. x 的平方根 - 力扣（LeetCode）
解决思路：我们可以将从1到x的所有数的平方枚举出来，并将该平方数与x作比较，这就会天然的把所有平方数分成两个区间，分别是 当前数>=x 和 当前数<x 两个区间，这样就具有了二段性，即
结合模板我们可以得到如下代码
题目链接：35. 搜索插入位置 - 力扣（LeetCode）
解析：根据示例1与示例2我们可以发现，目标索引左边的均<target，右边的均>=target，那么根据二段性有
我们就可以得到如下代码
题目链接：852. 山脉数组的峰顶索引 - 力扣（LeetCode）
解析：根据题目我们可以知道，存在一个山顶它的左边均满足arr[mid] > arr[mid-1]，它的右边均满足arr[mid] < arr[mid-1]，因此它满足二段性，即
结合模板可以得到
题目链接：162. 寻找峰值 - 力扣（LeetCode）
解析：这道题与上面的第三题类似，但是却又有些不同，由于这里是找到任意一个峰顶，因此我们还是可以如下分析
结合模板有
题目链接：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
解析：我们简要分析一下可以发现，这个数组整体呈现先上升，然后最低，再然后上升的趋势，由整个趋势我们可以看出，我们可以以最右边的数据做基准值，前一段上升趋势的数值均大于此基准值，而后一段上升趋势的数值均小于等于此基准值，即
结合模板有
同样的我们也可以使用第一个元素作为基准值，即
代码如下
题目链接：LCR 173. 点名 - 力扣（LeetCode）
解析：我们稍加分析可以发现，在缺席的同学处之前mid==arr[mid]，在缺席的同学之后mid>arr[mid]，即
结合模板有