前言
在算法的世界里,二分算法如同一把精准的钥匙,能快速开启有序数据的大门。无论是经典的有序序列查找,还是复杂的'最小值最大'类问题,二分思想都以惊人的效率(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};
}
};


