一.二分查找算法简介
1. 特点
二分查找细节繁多，边界条件处理不当极易出现死循环；但只要吃透边界逻辑，本质上是原理简单的算法。
2. 学习侧重点
补充小说明
- 朴素二分：适合数组元素不重复，只需要判断元素是否存在的场景。
- 左右边界二分：适合数组存在重复元素，需要查找目标的左右边界的场景，面试笔试高频。
- 坑点：mid 的溢出问题、while循环条件、left/right 更新语句，这三处是死循环高发位置。
二.算法练习
1.二分查找
a.题目描述：
b.题⽬链接：
704. 二分查找 – 力扣（LeetCode）
c.算法流程：
朴素二分查找（左闭右闭区间）流程
- a. 定义 left、right 指针，分别指向数组查找区间的左右边界。
- b. 求取当前待查找区间的中间点 mid，对比 arr[mid] 与目标值 target，分为三种情况：
- 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，也就避开了死循环。
它们只差两处
| 中点计算 | 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.题目链接：
35. 搜索插入位置 – 力扣（LeetCode）
c.算法流程：
- a. 分析插入位置两侧区间元素特征： 设插入位置下标为 index，区间满足：
- b. 定义 left、right 作为查找区间的左右边界，根据 nums[mid] 与目标值 target 的大小关系，更新查找区间：
- c. 循环终止条件：当区间收缩至 left == right（区间长度为 1），此时 left（或 right）的值，就是目标元素的插入位置。
d.代码实现：
4.x 的平方根
a.题目描述：
b.题目链接：
69. x 的平方根 – 力扣（LeetCode）
c.算法流程：
设 x 的平⽅根的最终结果为 index ：
- a. 分析 index 左右两次数据的特点：
因此可以使⽤⼆分查找算法。
d.代码实现：
5.山峰数组的峰顶索引
a.题目描述：
b.题目链接：
852. 山脉数组的峰顶索引 – 力扣（LeetCode）
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位置元素趋势，更新查找区间：
c. 循环结束，找到峰值位置。
d.代码实现：
6.寻找峰值
a.题目描述：
b.题目链接：
162. 寻找峰值 – 力扣（LeetCode）
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] 的大小关系更新区间：
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落点划分下一轮查找区间：
c. 直到查找区间收缩至长度为 1（left == right），此时left（或right）即为所求 C 点。
d.代码实现：
8.0〜n-1 中缺失的数字
a.题目描述：
b.题目链接：
LCR 173. 点名 – 力扣（LeetCode）
c.算法流程：
a. 分析数组二段性： 本题存在 O (N) 的暴力解法，这里只介绍最优二分解法。数组为升序排列：
- 第一个缺失位置的左侧：数组元素值与数组下标相等；
- 第一个缺失位置的右侧：数组元素值与数组下标不相等。 具备二段性，可以使用二分查找求解。
b. 定义left、right作为查找区间的左右边界，取中间点mid，根据nums[mid]与下标mid的关系更新查找区间：
c. 直到查找区间收缩至长度为 1（left == right），此时left（或right）即为第一个缺失的正整数。
d.代码实现：
