前言
二分查找的核心思想很简单：每次把搜索范围砍掉一半。但刷题时会发现，不同题目的写法差别很大——while(left < right) 还是 while(left <= right)？left = mid + 1 还是 left = mid？mid 什么时候要向上取整？
这篇文章按难度递进，从最经典的 704 开始，经过边界搜索、峰值查找、旋转数组、二维矩阵，最后到三道应用题，覆盖二分查找的主流题型。每个题在讲清楚解法的同时，会说明循环条件和指针移动的缘由。
704. 二分查找 — 一切从这开始
LeetCode 704 — 二分查找 (Easy)
在一个升序数组中找 target，找到返回下标，否则返回 -1。
这是二分查找的「标准形态」：数组全局有序、无重复元素、查找精确值。
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
区间 [left, right] 中的每一个元素都可能是答案，当 left == right 时区间里还有一个元素没检查，必须再进一次循环，所以用 while(left <= right)。写成 left < right 的话单元素数组会直接跳过，永远返回 -1。nums[mid] 已经在循环开头跟 target 比较过，确定不等于 target，可以把它从搜索区间里移除，所以边界收紧到 mid ± 1。
这就是二分查找的基础模板，后面的所有变体都建立在此之上，只是根据需求不同调整了循环条件和边界移动方式。
34. 在排序数组中查找元素的第一个和最后一个位置
LeetCode 34 — 在排序数组中查找元素的第一个和最后一个位置 (Medium)
给定一个升序整数数组
nums和一个目标值target，找出target在数组中的起始位置和结束位置。如果数组中不存在target，返回[-1, -1]。要求时间复杂度 O(log n)。
求解思路
直接的想法是先用基础二分找到任意一个 target，然后向两边线性扫描找边界。但这样在最坏情况下——比如整个数组全是同一个 target——会退化成 O(n)，失去了二分的优势。
核心问题是如何用二分直接找到边界。找到 target 本身不难，难的是找到第一个出现位置和最后一个出现位置。换个问法：
- 找左边界 = 找第一个 ≥ target 的位置
- 找右边界 = 找第一个 > target 的位置，再减 1
也就是说，把「找开始和结束」转化为两次边界查询。而边界查询可以统一为：在一个有序数组中，找第一个满足某个条件的位置。
在经典二分中，找不到 target 时 left 和 right 自然交错，循环结束即可判断。但在边界查询中，满足条件和不满足条件的结果混在一起——比如找第一个 ≥ target 的位置，当 nums[mid] >= target 时往左走，但 mid 本身就是一个候选答案，必须先记录再收缩。用 ans 变量保存最近一次满足条件的 mid，同时 right = mid - 1 继续往左试探；不满足条件时 left = mid + 1 往右走。这个「记录 + 收缩」的模式是二分查找处理边界问题的核心技巧。
int binarySearch(const vector<int>& nums, int target, bool lower) {
int left = 0, right = nums.size() - 1, ans = nums.size();
while (left <= right) {
int mid = left + (right - left) / 2;
// lower=true: 找第一个 >= target → 满足条件往左搜
// lower=false: 找第一个 > target → 满足条件往左搜
if (nums[mid] > target || (lower && nums[mid] >= target)) {
ans = mid; // 记录候选，继续缩小范围
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftIdx = binarySearch(nums, target, true); // 第一个 >= target
int rightIdx = binarySearch(nums, target, false) - 1; // 第一个 > target 再 -1
if (leftIdx <= rightIdx && nums[leftIdx] == target && nums[rightIdx] == target) {
return {leftIdx, rightIdx};
}
return {-1, -1};
}
复杂度： 时间 O(log n)，两次二分；空间 O(1)。
LCR 172 — 统计 target 出现次数
LeetCode LCR 172 和 34 的代码完全一致，区别只在于最后返回的是 rightIdx - leftIdx + 1（即 target 的个数）。理解了 34，这道题自然就过了，不再展开。
162. 寻找峰值
LeetCode 162 — 寻找峰值
给定一个整数数组
nums，保证相邻元素不相等。峰值元素是指值严格大于左右相邻元素的元素。数组可能存在多个峰值，返回任意一个峰值的下标即可。数组边界外的元素视为负无穷（即nums[-1] = nums[n] = -∞），这保证了数组至少存在一个峰值。
求解思路
最直接的想法当然是线性扫描：只要碰到一个 nums[i] > nums[i+1]，那 i 就是峰值——因为在它之前一直是上升的，突然下降了，这个拐点就是峰值。这个 O(n) 的解法已经能通过，但我们可以更快。
关键观察：取数组中任意位置 mid，看它和右边邻居 nums[mid+1] 的关系。如果 nums[mid] > nums[mid+1]，说明从 mid 开始已经在走下坡路了——那么 mid 及其左侧一定存在一个峰值。反之如果 nums[mid] < nums[mid+1]，还在上坡，峰值一定在 mid 右侧。数组两端视为负无穷保证了任何数组都至少有一个峰值。
这就把问题转化成了二分：每次比较 mid 和 mid+1，根据上坡/下坡方向决定往哪边走。因为每次都能保证目标半区一定包含峰值，二分一定收敛到正确答案。
这个二分不靠 nums[mid] == target 终止——没有 target 给你比较。我们是在不断缩小区间，直到区间只剩一个元素，那个元素就是峰值。因此用 while(left < right)，当 left == right 时区间只有一个元素，就是答案，不需要再进入循环。
当 nums[mid] > nums[mid+1] 时，mid 本身比右边大，可能就是峰值，所以 right = mid 保留这个候选。nums[mid] < nums[mid+1] 时，mid 比右边小，绝对不可能是峰值，因此 left = mid + 1 丢弃它。
剩两个元素时，mid 等于 left（向下取整）：nums[mid] > nums[mid+1] 时 right = mid = left，区间缩小为 1；nums[mid] < nums[mid+1] 时 left = mid + 1 = right，区间也缩小为 1。两种情况都不会死循环。
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid; // mid 可能是峰值，保留
} else {
left = mid + 1; // mid 不可能是峰值，丢弃
}
}
return left; // left == right，即峰值下标
}
复杂度： 时间 O(log n)；空间 O(1)。
852. 山脉数组的峰顶索引
LeetCode 852 — 山脉数组的峰顶索引 (Medium)
给定一个长度至少为 3 的山脉数组
arr，满足存在某个下标i（0 < i < arr.length - 1）使得arr[0] < arr[1] < ... < arr[i]且arr[i] > arr[i+1] > ...。找出峰顶下标i。
这道题是 162 的特例——数组被限定为单峰形态，两端负无穷的条件天然满足。162 的代码可以直接复用，逻辑完全不变。和 162 唯一的不同是题目保证了峰值的唯一性，所以分析时连「任意一个峰值」的说明都不需要了，代码照搬即可：
int peakIndexInMountainArray(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > arr[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
复杂度： 时间 O(log n)；空间 O(1)。
658. 找到 K 个最接近的元素
LeetCode 658 — 找到 K 个最接近的元素
给定一个升序数组
arr和两个整数k、x，从数组中找出k个最接近x的元素。两个数a和b谁更接近x由|a - x|和|b - x|决定，距离相同时取较小的数。结果按升序排列返回。
求解思路
直接做法是把每个元素与 x 的距离算出来再排序取前 k 个，O(n log n)。但数组本身是有序的——这引出一个关键性质：最接近 x 的 k 个数一定是数组中连续的一段。因为如果最终结果不连续，假设我们选了 a 和 c 但跳过了中间的 b，那 b 离 x 一定比 a 或 c 更近（数组有序保证了这一点），矛盾。这个「结果连续」的发现是本题能上二分的基础——我们只需要找到这段长度为 k 的窗口的起始位置，而不是在 n 个元素中逐个挑选。
找起始位置可以用二分。衡量方式是看搜索区间的两个端点哪个离 x 更远——如果左端点比右端点远，说明窗口应该向右移。区间是 [arr[mid], arr[mid+k-1]]，下一个可能加入的是 arr[mid+k]。比较 x - arr[mid] 和 arr[mid+k] - x：
- 如果左边距离更大，说明 x 更靠近右边，窗口右移，
left = mid + 1 - 否则窗口保持或左移，
right = mid
我们要找的是长度为 k 的窗口的起始下标，起始下标最大不能超过 n - k，不然凑不够 k 个元素，所以 right 初始值是 arr.size() - k 而不是 arr.size() - 1。和 162 一样，我们在缩小找到最优起始位置，while(left < right) 就够用了。当左边距离不大于右边距离时，mid 作为窗口起点可能是最优的，不能丢弃，故 right = mid。
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0, right = arr.size() - k;
while (left < right) {
int mid = left + (right - left) / 2;
// 比较：丢掉 arr[mid]，加入 arr[mid+k] 划不划算
if (x - arr[mid] > arr[mid + k] - x) {
left = mid + 1; // 右边更近，窗口右移
} else {
right = mid; // 左边更近或相等，保留 mid（相等取小值）
}
}
return vector<int>(arr.begin() + left, arr.begin() + left + k);
}
复杂度： 时间 O(log n + k)，二分找起点 O(log n)，构造结果 O(k)；空间 O(1)（输出数组不计入）。
33. 搜索旋转排序数组
LeetCode 33 — 搜索旋转排序数组 (Medium)
一个原本严格升序的数组在某个未知下标处进行了旋转——将数组后若干元素整体移到前面。例如
[1,2,3,4,5,6,7]在下标 3 处旋转得到[4,5,6,7,1,2,3]。给定旋转后的数组和一个目标值target，找出target的下标，不存在则返回 -1。数组元素互不相同，时间复杂度要求 O(log n)。
求解思路
数组被旋转后变成了两段各自有序的区间，比如 [4,5,6,7,1,2,3]，前半段 [4,5,6,7] 升序，后半段 [1,2,3] 升序，但整体不再有序。这看起来不能用二分了——二分的前提是数组有序。
但是，取任意一个位置 mid，它一定落在其中一段有序区间里。怎么区分 mid 在左半段还是右半段？比较 nums[left] 和 nums[mid]：
- 如果
nums[left] <= nums[mid]，说明从 left 到 mid 这一段没有跨过切口，是严格有序的 - 否则，mid 到 right 这一段是有序的
确定哪一半有序之后，就可以判断 target 是否落在有序的那一半的范围内。如果在，就对该有序半段做标准二分；如果不在，target 必然在另一半，继续在另一半上重复这个逻辑。
和 704 一致，需要检查 nums[mid] == target 且每个元素都可能是答案，所以用 while(left <= right)。nums[mid] 已确定不等于 target，从搜索区间丢弃，故 left = mid + 1、right = mid - 1。
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) { // 左半段有序
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // target 在左半段内
} else {
left = mid + 1; // target 在右半段
}
} else { // 右半段有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // target 在右半段内
} else {
right = mid - 1; // target 在左半段
}
}
}
return -1;
}
复杂度： 时间 O(log n)；空间 O(1)。
注意 nums[left] <= nums[mid] 的条件用的是 <= 而不是 <：当 left == mid 时，搜索区间仅剩两个元素，nums[left]已经检查过不是target，所以应该进入右半段，用 <= 将其归为左半段有序，可以正常进入右半段，否则会进入左半段返回-1。
81. 搜索旋转排序数组 II
LeetCode 81 — 搜索旋转排序数组 II (Medium)
和 33 完全相同的设定——旋转后的升序数组中搜索
target——但允许数组中出现重复元素。返回true或false。
求解思路
33 的解法依赖一个前提：比较 nums[left] 和 nums[mid] 就能确定哪一半有序。但重复元素打破了这个前提——当 nums[left] == nums[mid] 时，无法判断左半段是否有序。比如 [1,0,1,1,1] 中 left=0, mid=2，nums[left] == nums[mid] == 1，但左半段并不有序；而 [1,1,1,0,1] 中同样的 left=0, mid=2，nums[left] == nums[mid] == 1，左半段是有序的。两个数组在 mid 处的信息完全一样，但结构不同。
处理方式：遇到 nums[left] == nums[mid] 时，无法获得有用信息，只能将 left 右移一位，丢掉这个重复元素。这是安全的——因为 nums[left] 的值在 mid 处还有一个副本，不会丢失 target。其余逻辑和 33 完全一致。
由于最坏情况下每次只能移动一步（全相等数组），时间复杂度退化到 O(n)，但平均仍是 O(log n)。注意返回值从 33 的下标变为 bool。
bool search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
// 无法判断左半段是否有序，安全收缩左边界
if (nums[left] == nums[mid]) {
left++;
continue;
}
if (nums[left] < nums[mid]) { // 左半段有序
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右半段有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
复杂度： 平均 O(log n)，最坏 O(n)（全相等时每次 left++ 只移动一步）；空间 O(1)。
153. 寻找旋转排序数组中的最小值
LeetCode 153 — 寻找旋转排序数组中的最小值
一个原本严格升序的数组在某个未知下标处旋转过一次（定义和 33 相同），数组元素互不相同。找出旋转后数组中的最小元素。要求时间复杂度 O(log n)。例如
[4,5,6,7,1,2,3]的最小值为 1。
求解思路
旋转前数组是 [0,1,2,3,4,5,6]，旋转后变成 [4,5,6,0,1,2,3]。观察发现：左半段的所有元素都大于右半段的所有元素。最小值就是那个切口位置，也是整个数组唯一一个比左边元素小的元素。虽然数组整体不再有序，但两段各自有序这个性质，仍然给了二分搜索的可能——关键在于找到一个能判断最小值在 mid 左边还是右边的依据。
用 nums[mid] 和 nums[right] 比较即可：
nums[mid] > nums[right]：mid 落在了左半段（较大的那半），最小值一定在 mid 右边。因为右半段全部小于左半段，mid 连最大的右半段元素都比不过，说明 mid 还在高处，left = mid + 1。nums[mid] < nums[right]：mid 落在了右半段（较小的那半）。最小值可能在 mid 位置，也可能在 mid 左边。所以right = mid，保留 mid 这个候选。
用 right 做参照是因为 nums[right] 一定在右半段中（或本身就是最小值），能一致地反映 mid 在高区还是低区。用 left 做参照的话，left 在旋转 0 次时就在低区、旋转非 0 次时在高区，判断逻辑不一致。题目保证元素互不相同，所以不会出现 nums[mid] == nums[right] 的情况。
和 162 一样在缩小区间找位置，用 while(left < right) 即可。剩两个元素时 mid = left（向下取整）：nums[mid] > nums[right] 则 left = mid + 1 = right，nums[mid] < nums[right] 则 right = mid = left，都能收敛到单元素。
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1; // mid 在左半段，最小值在右侧
} else {
right = mid; // mid 在右半段，最小值在左侧（含 mid）
}
}
return nums[right]; // left == right
}
复杂度： 时间 O(log n)；空间 O(1)。
延伸：找最大值
对称推导——如果把标准从「找最小值」换成「找最大值」，只需要做两处调整：
- 参照物从
right换成left（因为最大值一定在左半段） - 与 left 比较后可能出现
left = mid，此时 mid 必须向上取整，即mid = left + (right - left + 1) / 2，否则只剩两个元素时会死循环
int findMax(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2; // 向上取整！
if (nums[mid] < nums[left]) {
right = mid - 1; // mid 在右半段，最大值在左侧
} else {
left = mid; // mid 在左半段，最大值在右侧（含 mid）
}
}
return nums[right];
}
找最大值时必须向上取整。因为剩两个元素时如果用向下取整，mid = left，若 nums[mid] >= nums[left]，left = mid 会让 left 原地不动，死循环。向上取整后 mid = right，left = mid 直接收敛。二分中出现 left = mid 时，mid 必须向上取整，这是一个硬规则。
154. 寻找旋转排序数组中的最小值 II
LeetCode 154 — 寻找旋转排序数组中的最小值 II
和 153 相同——在旋转过的升序数组中找最小值——但数组允许重复元素。例如
[2,2,2,0,1]返回 0。重复元素打破了 153 中nums[mid]与nums[right]严格不等的前提，需要额外处理。
求解思路
在 153 中，nums[mid] 与 nums[right] 的比较只有大于和小于两种情况，方向明确。重复元素引入了第三种情况：nums[mid] == nums[right]，此时无法判断 mid 在左半段还是右半段。比如 [1,3,3,3,3]（旋转 0 次）中，mid 在左半段但和 right 相等；[3,3,3,1,3]（旋转 3 次）中，mid 在左半段且同样和 right 相等。两个数组的 mid-right 关系完全一样，但最小值位置不同——一个在左侧，一个在右侧。153 的逻辑在这里失效了。
解法与34思路相同，相等时只安全丢弃一个元素，遇到相等时，right--。既然 nums[mid] == nums[right]，right 这个元素的值在 mid 处也有一个副本，丢掉 right 不会丢失最小值。每次只安全地移除一个元素，直到 nums[mid] 和 nums[right] 重新分出大小，就可以继续走 153 的二分逻辑。
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] == nums[right]) {
right--; // 安全收缩，不丢失最小值
} else {
right = mid;
}
}
return nums[right];
}
复杂度： 平均 O(log n)，最坏 O(n)（全相等时 right-- 每次只移动一步）；空间 O(1)。
延伸：找最大值（允许重复）
对称地，相等时 left++：
int findMax(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2; // 向上取整
if (nums[mid] < nums[left]) {
right = mid - 1;
} else if (nums[mid] == nums[left]) {
left++; // 安全收缩
} else {
left = mid;
}
}
return nums[right];
}
74. 搜索二维矩阵
LeetCode 74 — 搜索二维矩阵 (Medium)
给定一个
m x n的矩阵，每行按升序排列，且每行的第一个元素大于上一行的最后一个元素。判断一个目标值target是否存在于矩阵中。例如：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]，target = 3返回true。
求解思路
题目给的条件很特别——不仅每行有序，而且行与行之间也有严格的大小关系。这等价于把整个矩阵按行展开，得到一个全局有序的一维数组。所以最简单的做法是把二维坐标映射成一维，做一次全局二分，O(log(m*n))。
另一种做法是两次二分：先对第一列二分确定 target 落在哪一行（找最后一个 matrix[row][0] <= target 的行），再对该行做标准二分。两种做法的效率相同，但两次二分能更清晰地展示二分查找在二维场景下的分解思路。
第一次二分 — 找行： 和 34 的边界搜索类似，需要记录「最后一个满足条件的行」。matrix[mid][0] == target 时直接返回 true；matrix[mid][0] < target 时，mid 这一行是候选，存到 rowans 然后继续往右（下面）找更大的行首；matrix[mid][0] > target 时往左找。
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
// 第一次二分：找行 — 最后一个 matrix[row][0] <= target 的行
int left = 0, right = m - 1, row = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[mid][0] == target) return true;
else if (matrix[mid][0] < target) {
row = mid; // 候选行
left = mid + 1;
} else {
right = mid - 1;
}
}
if (row == -1) return false;
// 第二次二分：在该行内找 target
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (matrix[row][mid] == target) return true;
else if (matrix[row][mid] < target) l = mid + 1;
else r = mid - 1;
}
return false;
}
复杂度： 时间 O(log m + log n)；空间 O(1)。
875. 爱吃香蕉的珂珂
LeetCode 875 — 爱吃香蕉的珂珂 (Medium)
有
n堆香蕉，第i堆有piles[i]根香蕉。珂珂吃香蕉的速度是每小时k根。每小时她只选一堆香蕉吃：如果这堆香蕉少于k根，她吃完这堆后这一小时不再吃其他堆；如果多于k根，她吃完k根后这一小时也结束。警卫将在h小时后回来，求珂珂能在h小时内吃完所有香蕉的最小速度k。
求解思路
这道题和前面所有题目的根本区别在于：搜索的不是数组中的某个元素，而是一个未知的速度值。如何想到二分？关键有两点：第一，直接求最小速度 k 不好下手，但验证一个给定速度 k 能否在 h 小时内吃完非常容易——遍历每堆香蕉，ceil((double)piles[i] / k) 累加即可，O(n) 完成。第二，速度越快越容易在 h 小时内吃完——这说明问题具有单调性：如果速度 v 可行，那么所有大于 v 的速度也可行；如果速度 v 不可行，那么所有小于 v 的速度也不可行。单调性意味着可以在答案的取值范围内二分搜索。
速度的范围：最慢是 1（每小时至少吃 1 根），最快是 max(piles)（对最⼤那堆也能一小时吃完，再快没有意义）。在这 [1, max(piles)] 上二分找最小可行速度。和峰值、最小值题目一样，在缩小区间找最小值，用 while(left < right) 即可。判定返回 true 时 mid 可行，right = mid 保留候选；返回 false 时 mid 太慢，left = mid + 1 丢弃。
int minEatingSpeed(vector<int>& piles, int h) {
int maxPile = 0;
for (int p : piles) maxPile = max(maxPile, p);
int left = 1, right = maxPile;
while (left < right) {
int mid = left + (right - left) / 2;
if (canEat(piles, h, mid)) {
right = mid; // mid 可行，尝试更小的
} else {
left = mid + 1; // mid 不可行，必须加快
}
}
return right;
}
bool canEat(vector<int>& piles, int h, int speed) {
int time = 0;
for (int p : piles) {
time += (p + speed - 1) / speed; // 向上取整
}
return time <= h;
}
复杂度： 时间 O(n · log M)，M = max(piles)；空间 O(1)。
1011. 在 D 天内送达包裹的能力
LeetCode 1011 — 在 D 天内送达包裹的能力 (Medium)
传送带上的包裹按给定顺序排列，第
i个包裹的重量为weights[i]。每天按包裹顺序往船上装货，当累计重量超过船的运力时，超出的包裹留到下一天。必须在days天内运完所有包裹，求船的最低运力。
求解思路
和 875 是同一套思路：直接求最低运力不好下手，但验证一个给定运力能否在 days 天内运完很简单——按顺序装，当天重量超标就留到第二天，最后比较所需天数是否 ≤ days。运力越大所需天数越少，同样是单调性问题。
运力的下界是 max(weights)（至少得运走最重的单个包裹），上界是 sum(weights)（一天全部运走）。在这个范围内二分搜索最小可行运力。
int shipWithinDays(vector<int>& weights, int days) {
int maxW = 0, sumW = 0;
for (int w : weights) {
maxW = max(maxW, w);
sumW += w;
}
int left = maxW, right = sumW;
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
bool canShip(vector<int>& weights, int days, int capacity) {
int dayCount = 1, curLoad = 0;
for (int w : weights) {
if (curLoad + w > capacity) {
dayCount++;
curLoad = 0;
}
curLoad += w;
}
return dayCount <= days;
}
复杂度： 时间 O(n · log S)，S = sum(weights)；空间 O(1)。
410. 分割数组的最大值
LeetCode 410 — 分割数组的最大值
给定一个非负整数数组
nums和一个整数k，将nums分成k个非空连续子数组。一种分割方式会产生 k 个子数组各自的和，取其中最大值作为这种分割方式的代价。求所有分割方式中这个代价的最小值。例如nums = [7,2,5,10,8],k = 2，最佳分割为[7,2,5]和[10,8]，代价为 18。
求解思路
这道题一眼看过去不像二分——题目要的是分割数组，感觉像动态规划。但换个角度：我们要找的是子数组和的上限，使得在这个限制下能用不超过 k 段切完整个数组。如果给定的上限越大，所需段数就越少——单调性出现了。验证一个上限 mid 是否可行也很简单：贪心地往每段塞数，超过 mid 就另起一段，最后统计段数是否 ≤ k。
这和 1011 本质是同一道题：1011 是「给定天数限制求最小运力」，410 是「给定分段数限制求最小的最大段和」，判定逻辑完全一样。下界是 max(nums)（任何一段的和至少得大于等于最大元素），上界是 sum(nums)（只分一段）。
int splitArray(vector<int>& nums, int k) {
int left = 0, right = 0;
for (int x : nums) {
left = max(left, x);
right += x;
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canSplit(nums, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
bool canSplit(vector<int>& nums, int k, int limit) {
int segments = 1, curSum = 0;
for (int x : nums) {
if (curSum + x > limit) {
segments++;
curSum = 0;
}
curSum += x;
}
return segments <= k;
}
复杂度： 时间 O(n · log S)，S = sum(nums)；空间 O(1)。
875、1011、410 这三道题的代码结构几乎完全一样——区别只在搜索范围和判定函数的具体逻辑。确定答案的单调范围 → 写判定函数 → 在 [left, right] 上二分搜索满足判定条件的最小/最大值。
总结
面对一道二分搜索题目，可以按以下顺序进行思考。
第一步：循环条件 — 能不能在循环里直接判定 mid 是不是答案？
这是选择 <= 还是 < 的根本依据。
能直接判定 → while(left <= right)。典型情况是「找某个值」：nums[mid] == target 命中就返回了（704）；或者「找第一个满足某条件的位置」，nums[mid] >= target 时 mid 就是候选，拿 ans 记录下来继续往左搜（34）。总之每一轮都能明确回答「mid 是或不是答案」，答案在循环过程中已经确定，区间搜空就结束。
不能直接判定 → while(left < right)。典型情况是「mid 是否答案需要上下文才能知道」：峰值需要跟左右邻居比较才知道是不是峰（162），最小值需要跟 right 比较才知道在左半还是右半（153），给定速度需要跑一遍验证才知道行不行（875）。这些场景里 mid 只能告诉你该往哪边走，不能直接判对错。只能不断收缩区间，直到只剩一个元素——那就是答案。
第二步：指针移动 — mid 有没有可能是答案？
在 while(left <= right) 中，mid 已经被判定过了，不是答案就丢掉，所以一律 left = mid + 1 / right = mid - 1。
在 while(left < right) 中，每轮只判断了方向，mid 可能仍然是答案：
- 当答案落在左侧且可能包含 mid 时 →
right = mid（保留 mid） - 当答案落在右侧且可能包含 mid 时 →
left = mid（保留 mid） - 当答案落在右侧且 mid 绝对不可能是答案时 →
left = mid + 1（丢弃 mid） - 当答案落在左侧且 mid 绝对不可能是答案时 →
right = mid - 1（丢弃 mid）
什么时候 mid 绝对不可能是答案？比如 162 中 nums[mid] < nums[mid+1]，mid 比右边小，在上坡，峰值一定在右侧，mid 不可能是峰值。比如 153 中 nums[mid] > nums[right]，mid 在高区，最小值一定在右边，mid 不可能是最小值。
第三步：mid 取整条件 — 出现 left = mid 时向上取整。
绝大多数情况向下取整：mid = left + (right - left) / 2。唯一需要向上取整的场景是代码中出现了 left = mid：此时 mid = left + (right - left + 1) / 2，否则剩两个元素时 left = mid 会让 left 原地不动，死循环。全文只有「找最大值」这类对称推导里用到它。
二分搜索的应用（875、1011、410）：
这类题目初看不像二分——题目描述里没有排序数组，也没有搜索目标。识别它的线索是：直接求最优值不好下手，但验证一个候选值是否可行非常容易，且候选值存在单调性。碰到这三条，就可以在候选值范围上二分。代码结构统一：while(left < right) + right = mid / left = mid + 1。
相关题目
- LeetCode 704 — 二分查找
- LeetCode 34 — 在排序数组中查找元素的第一个和最后一个位置
- LCR 172 — 统计目标成绩的出现次数
- LeetCode 162 — 寻找峰值
- LeetCode 852 — 山脉数组的峰顶索引
- LeetCode 658 — 找到 K 个最接近的元素
- LeetCode 33 — 搜索旋转排序数组
- LeetCode 81 — 搜索旋转排序数组 II
- LeetCode 153 — 寻找旋转排序数组中的最小值
- LeetCode 154 — 寻找旋转排序数组中的最小值 II
- LeetCode 74 — 搜索二维矩阵
- LeetCode 875 — 爱吃香蕉的珂珂
- LeetCode 1011 — 在 D 天内送达包裹的能力
- LeetCode 410 — 分割数组的最大值