> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/er-fen/er-fen-zong-jie.md).

# 二分总结

二分法一般应用在数组上, 在数组中以$$O(\log{N})$$的时间复杂度进行**查找**. 首先设置**左右端点**, 找到中间点, 一般根据`(left + right) // 2`找到中间点. 然后根据中间点的值与左右端点值的大小, 以及不同题目中各异的逻辑关系, 将**其中的一个端点**移动到**中间点上**或**中间点附近**, 完成一轮的迭代. 之后重复这个步骤, 直到满足停止条件, 这个条件一般是**左右端点汇聚在一个位置时**, 或**左右端点越界, 左在右侧, 右在左侧**, 这个条件也是要根据具体的题目确定. 最终左端点(普遍情况)或右端点所在的位置, 或这个位置对应的值就是最后的答案.

其中由很多细节:

* 端点移动的细节: 左右端点向中间移动时方案不同; 移动到中间点, 还是中间点邻近的一个位置
* 终止条件: 左右端点处于同一个端点时停止; 左右交叉后停止
* 前两者的结合, 终止条件的变化, 很可能就会导致移动细节的变化
* 其他

## 中点与移动

一般求新的中点使用公式`(left + right) // 2`. 由于使用的是整除, 所以存在 $$\text{left} \le \text{mid} \lt \text{right}$$, 即如果`left`和`right`不相等, 得到的`mid`是一定小于右端索引, 不小于左端索引, **但是可能与左端相等**, 即`mid`就是`left`.

这点非常重要. 因为我们设计移动策略的时候, 要**保证端点不能原地移动**, 否则左右端点经过一轮迭代后没有移动, 求出的中间点还是一样的, **会陷入死循环**.

所以在制定**左侧端点**的移动策略时, 一般在满足特定条件后需要移动左端点时, 会使`left = mid + 1`, 以避免最终原地踏步, 陷入死循环. 而右侧端点使得`right = mid`即可.

当然能否这样移动, 不同题目还需要进行不同的考虑.

## 终止条件

如果是左右端点处于同一个端点时停止, 则循环条件应写为`while left < right`; 如果是左右交叉后停止, 循环条件应写为`while left <= right`. 在实际题目中设置终止条件时, 可以多考虑以下点.

### 如何到达`left == right`

按照`left = mid + 1`和`right = mid`的移动策略, 一轮迭代之后, 满足`left == right`, 有两种情况.

#### 移动右结点

要求迭代前`left`与`right`相邻, 即`left = right - 1`, **两者确定的子数组长度为2**. `mid = (left + right) // 2 = left`, 两者相遇.

#### 移动左节点

根据`mid = (left + right) // 2 + 1 = right`, 可以得到此时`left = right - 2`, **两者确定的子数组长度为3**.