一.二分查找算法简介
1. 特点
二分查找细节繁多，边界条件处理不当极易出现死循环；但只要吃透边界逻辑，本质上是原理简单的算法。
2. 学习侧重点
- 算法原理（重点） 核心思想：利用数组有序特性，不断取区间中点，通过比较中点值和目标值，折半缩小查找范围，快速定位目标。
- 二分模板（重点） 不要死记硬背，理解区间定义（左闭右闭 / 左闭右开）之后再记忆模板。 一共 3 套常用模板：
- 朴素二分模板：查找是否存在目标值，简单，但有使用局限；
- 查找左边界二分模板：找到目标元素第一次出现的位置，边界细节多；
- 查找右边界二分模板：找到目标元素最后一次出现的位置，边界细节多。
补充小说明
- 朴素二分：适合数组元素不重复，只需要判断元素是否存在的场景。
- 左右边界二分：适合数组存在重复元素，需要查找目标的左右边界的场景，面试笔试高频。
- 坑点：
mid的溢出问题、while循环条件、left/right更新语句，这三处是死循环高发位置。
二.算法练习
1.二分查找
a.题目描述：
b.题⽬链接：
c.算法流程：
朴素二分查找（左闭右闭区间）流程
- a. 定义
left、right指针，分别指向数组查找区间的左右边界。 - b. 求取当前待查找区间的中间点
mid，对比arr[mid]与目标值target，分为三种情况：
- i.
arr[mid] == target：已找到目标元素，返回下标mid；- ii.
arr[mid] > target：区间[mid, right]内所有值均大于 target，舍弃右半区间，更新区间为[left, mid - 1]，设置right = mid - 1，重复步骤 b；- iii.
arr[mid] < target：区间[left, mid]内所有值均小于 target，舍弃左半区间，更新区间为[mid + 1, right]，设置left = mid + 1，重复步骤 b；
- c. 当
left > right（左右指针错开），代表全区间查找完毕，不存在目标元素，返回-1。
d.代码实现：
2.在排序数组中查找元素的第⼀个和最后⼀个位置
a.题目描述：
b.题目链接：
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
c.算法流程
整体思路是把这件事拆成两个独立的问题：找左端点一次二分，找右端点再二分一次。两次的循环条件相同，但划分依据、中点取整和收缩方式都不一样。
d.代码实现:
⼆分查找算法模板总结：
二分查找最难的不是原理，而是边界的细节。真正常用的其实就只有下面两个模板：
// 模板 A：找左边界
while (left < right)
{
int mid = left + (right - left) / 2;
if (......) left = mid + 1;
else right = mid;
}// 模板 B：找右边界
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (......) left = mid;
else right = mid - 1;
}两个模板的循环条件都是 left < right，这一点很关键：它意味着二分结束时 left 和 right 一定相等，那个位置就是候选答案。所以循环里不需要判断 left == right，也就避开了死循环。
它们只差两处
| 模板 A（左边界） | 模板 B（右边界） | |
|---|---|---|
| 中点计算 | left + (right - left) / 2（下取整） | left + (right - left + 1) / 2（上取整） |
| 保留 mid 的那一支 | else --> right = mid | if --> left = mid |
除了这两处，其余完全一样。
为什么这两处必须这样配对
根源是防死循环。
mid ± 1 那一支是安全的，因为它必然让区间至少缩小一个位置。但裸 mid 那一支有可能原地不动——当区间只剩两个元素、中点恰好落在那一端时，区间就不会缩小。
举个最小例子，假设此刻区间是 left = 0, right = 1：
模板 A 用的是 right = mid
下取整 --> mid = 0 = left
走 else 这一支：right = mid = 0
--> 区间从 [0,1] 变成 [0,0] 缩小了，安全
上取整 --> mid = 1 = right
走 else 这一支：right = mid = 1
--> 区间还是 [0,1] 没变！死循环所以模板 A 必须用下取整。模板 B 的情况正好相反，它用的是 left = mid，必须用上取整，否则同样会卡住。
这就引出一句很好用的口诀：
让下面出现
-1的时候，上面就加+1。
这里"下面"指 if-else 分支，"上面"指中点计算。对照一下：
- 模板 A 的分支是
mid + 1和裸mid，没有-1→ 中点不加 1，用下取整- 模板 B 的分支是裸
mid和mid - 1，出现了-1→ 中点要加 1，用上取整
3.搜索插⼊位置
a.题目描述：
b.题目链接：
c.算法流程：
- a. 分析插入位置两侧区间元素特征： 设插入位置下标为
index，区间满足：
[left, index - 1]：区间内全部元素小于target；[index, right]：区间内全部元素大于或等于target。
- b. 定义
left、right作为查找区间的左右边界，根据nums[mid]与目标值target的大小关系，更新查找区间：
- i. 若
nums[mid] >= target：说明mid落在[index, right]区间，mid及其左侧有可能是目标插入点，更新查找区间为[left, mid]，即令right = mid，继续循环；- ii. 若
nums[mid] < target：说明mid落在[left, index - 1]区间，插入点一定在mid的右侧，更新查找区间为[mid + 1, right]，即令left = mid + 1，继续循环。
- c. 循环终止条件：当区间收缩至
left == right（区间长度为 1），此时left（或right）的值，就是目标元素的插入位置。
d.代码实现：
4.x 的平方根
a.题目描述：
b.题目链接：
c.算法流程：
设 x 的平⽅根的最终结果为 index ：
- a. 分析 index 左右两次数据的特点：
- [0, index] 之间的元素，平⽅之后都是⼩于等于 x 的；
- [index + 1, x] 之间的元素，平⽅之后都是⼤于 x 的。
因此可以使⽤⼆分查找算法。
d.代码实现：
5.山峰数组的峰顶索引
a.题目描述：
b.题目链接：
c.算法流程
a. 分析峰顶以及山峰两侧区间的元素特征：
- 峰顶元素：
arr[i] > arr[i - 1] && arr[i] > arr[i + 1]；- 峰顶左侧区间：元素呈上升趋势，满足
arr[i] > arr[i - 1] && arr[i] < arr[i + 1]；- 峰顶右侧区间：元素呈下降趋势，满足
arr[i] < arr[i - 1] && arr[i] > arr[i + 1]。b. 定义
left、right为查找区间左右边界，根据mid位置元素趋势，更新查找区间：
- i. 若
mid位置处于上升趋势：峰值一定在mid右侧，更新查找区间为[mid + 1, right]，即left = mid + 1，继续查找；- ii. 若
mid位置处于下降趋势：峰值一定在mid左侧，更新查找区间为[left, mid - 1]，即right = mid - 1，继续查找；- iii. 若
mid就是峰顶元素，直接返回mid下标。c. 循环结束，找到峰值位置。
d.代码实现：
6.寻找峰值
a.题目描述：
b.题目链接：
c.算法流程：
a. 分析数组二段性： 任取下标
i，对比arr[i]和arr[i+1]，存在两种情况：
arr[i] > arr[i + 1]：左侧区间一定存在峰值（数组两端等效负无穷），目标在左侧；arr[i] < arr[i + 1]：右侧区间一定存在峰值（数组两端等效负无穷），目标在右侧。 具备二段性，因此可以采用二分查找求解。b. 定义
left、right作为查找区间的左右边界，取中间点mid，根据arr[mid]与arr[mid+1]的大小关系更新区间：
- i. 若
arr[mid] > arr[mid + 1]：峰值存在于左半区间，更新查找区间为[left, mid]，即right = mid，继续查找；- ii. 若
arr[mid] < arr[mid + 1]：峰值存在于右半区间，更新查找区间为[mid + 1,right]，即left = mid + 1，继续查找。c. 直到查找区间收缩至
left == right，此时left（或right）即为峰值下标。
d.代码实现：
7.搜索旋转排序数组中的最⼩值
a.题目描述：
b.题目链接：
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
c.算法流程
a. 二分查找核心本质：找到判定条件，将查找区间一分为二。 C 点为待查找目标点。由图像可得区间性质：
[A，B]区间内所有点的值，严格大于 D 点的值；[C，D]区间内所有点的值，小于等于 D 点的值；- 特殊说明：当
[C，D]区间仅剩一个元素时，C 点的值可以等于 D 点的值。b. 定义
left、right为查找区间的左右边界，取中间点mid，根据mid落点划分下一轮查找区间：
- i. 若
mid落在[A，B]区间，即nums[mid] > D：目标在mid右侧，更新查找区间为[mid + 1，right]，即left = mid + 1，继续查找；- ii. 若
mid落在[C，D]区间，即nums[mid] <= D：目标在mid及左侧，更新查找区间为[left，mid]，即right = mid，继续查找。c. 直到查找区间收缩至长度为 1（
left == right），此时left（或right）即为所求 C 点。
d.代码实现：
8.0〜n-1 中缺失的数字
a.题目描述：
b.题目链接：
c.算法流程：
a. 分析数组二段性： 本题存在 O (N) 的暴力解法，这里只介绍最优二分解法。数组为升序排列：
- 第一个缺失位置的左侧：数组元素值与数组下标相等；
- 第一个缺失位置的右侧：数组元素值与数组下标不相等。 具备二段性，可以使用二分查找求解。
b. 定义
left、right作为查找区间的左右边界，取中间点mid，根据nums[mid]与下标mid的关系更新查找区间：
- i. 若
nums[mid] == mid：缺失位置一定在mid右侧，更新查找区间为[mid + 1, right]，即left = mid + 1，继续查找；- ii. 若
nums[mid] != mid：缺失位置在mid及其左侧，更新查找区间为[left, mid]，即right = mid，继续查找。c. 直到查找区间收缩至长度为 1（
left == right），此时left（或right）即为第一个缺失的正整数。
d.代码实现：
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2501_93351213/article/details/167393267
