前言
在算法的世界里，二分算法如同一把精准的钥匙，能快速开启有序数据的大门。无论是经典的有序序列查找，还是复杂的'最小值最大'类问题，二分思想都以惊人的效率（O(log n)）化繁为简，成为程序员必须掌握的核心技能。然而，许多初学者在运用二分时常常陷入边界不清、死循环或答案错误的窘境。本文将从二分的本质出发，深入剖析其原理与易错点，提供清晰可靠的模板，并带你走进 STL 中的二分利器。随后，我们将通过'二分查找'与'二分答案'两大实战板块，精选六道经典题目，从区间查询，到最优化决策，一步步拆解题意、推导思路、实现代码。
1. 二分算法
1.1 二分算法的相关概念
二分算法是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。
二分算法的原理以及模板其实是很简单的，主要的难点在于问题中的各种各样的细节问题。因此，大多数情况下，只是背会二分模板并不能解决题目，还要去处理各种乱七八糟的边界问题。
二分算法的核心：根据中点位置的值，判断最终解集是在左边区域还是在右边区域。如果确定一半区域，可以舍弃另一半区域，在有所求答案的区域内找。
1.2 二分算法的探讨
算法原理：
-
暴力解法： 从前往后扫描数组，时间复杂度是 O(N)，慢就慢在没有利用数组的有序性。 我们发现，假设要查找的数为 6，我们可以将这一串数分为两部分，计算中点为 12，则将 12 的左边分为小于 12 的区域，右边分为大于 12 的区域。因为 6 比 12 小，故 6 肯定在 12 的左侧区域，这样的话 12 右侧的区域就不用查找了。之后再在 12 的左侧按照以上的方式继续查找。此时我们发现解集中存在二段性，就可以用到二分算法了。
-
二分算法： 二分算法中需要解决两个位置，一个是起始位置，另一个是终止位置。
首先需要更新左右指针的位置：
细节问题：
(1) 查找起始位置：
- while 循环判断需要如何写：两种写法：
while(left < right)和while(left <= right)；应该选while(left < right)，另外一种写法会造成死循环。 - 求中点的方式：同样有两种写法：
(left + right) / 2和(left + right + 1) / 2；应该选(left + right) / 2，另外一种写法会造成死循环。
(2) 查找终止位置：
- while 循环判断需要如何写：两种写法：
while(left < right)和while(left <= right)；应该选while(left < right)，另外一种写法会造成死循环。 - 求中点的方式：同样有两种写法：
(left + right) / 2和(left + right + 1) / 2；应该选(left + right + 1) / 2，另外一种写法会造成死循环。
- while 循环判断需要如何写：两种写法：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
n = nums.();
(n == ) {, };
left = , right = n - ;
(left < right) {
mid = (left + right) / ;
(nums[mid] >= target) right = mid;
left = mid + ;
}
(nums[left] != target) {, };
releft = left;
left = , right = n - ;
(left < right) {
mid = (left + right + ) / ;
(nums[mid] <= target) left = mid;
right = mid - ;
}
{releft, left};
}
};
