二分查找——算法总结与教学指南

📚 算法核心思想

二分查找的本质

• 在有序集合中通过不断折半缩小搜索范围
• 每次比较都能排除一半的错误答案
• 核心前提：数据必须有序（直接或间接）

三种二分查找模式

🔧 通用解题框架

基础二分查找模板

int binarySearch(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; // 未找到
}

寻找边界的二分模板

// 寻找第一个 >= target 的位置（lower_bound）
int findFirstGreaterOrEqual(vector<int>& nums, int target) {
int left = 0, right = nums.size(); // 注意：右开区间

while (left < right) {
int mid = left + (right – left) / 2;

if (nums[mid] >= target) {
right = mid; // 保留mid，继续向左找
} else {
left = mid + 1; // 向右找
}
}

return left; // 第一个 >= target 的位置
}

🎯 问题识别技巧

什么时候用二分查找？

判断依据

// 如果是这些问题，考虑二分查找：
– "在排序数组中查找元素的第一个和最后一个位置"
– "寻找旋转排序数组中的最小值"
– "在 D 天内送达包裹的能力"（最优化问题）
– "制作 m 束花所需的最少天数"
– "分割数组的最大值"

🔍 关键决策点

1. 如何选择区间表示？

• 左闭右闭 [left, right]：while(left <= right)，更新时 mid±1
• 左闭右开 [left, right)：while(left < right)，更新时 left=mid+1 或 right=mid

2. 如何判断搜索方向？

// 不同问题的判断条件
if (nums[mid] == target) // 标准查找
if (nums[mid] >= target) // 寻找左边界
if (nums[mid] > target) // 寻找右边界
if (canFinish(piles, mid, h)) // 最优化问题（抽象条件）

3. 如何避免死循环？

• 确保每次循环区间都在缩小
• 注意 mid 的计算方式：mid = left + (right-left)/2（向下取整）
• 更新边界时至少移动一步：left = mid+1 或 right = mid-1

💡 经典问题分类与解法

类型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;
}

类型2：寻找边界

// 问题：在排序数组中查找元素的第一个和最后一个位置
vector<int> searchRange(vector<int>& nums, int target) {
// 找左边界：第一个 >= target 的位置
int left = lower_bound(nums.begin(), nums.end(), target) – nums.begin();

// 找右边界：第一个 > target 的位置 – 1
int right = upper_bound(nums.begin(), nums.end(), target) – nums.begin() – 1;

if (left <= right) return {left, right};
return {–1, –1};
}

类型3：旋转数组查找

// 问题：搜索旋转排序数组
int searchRotated(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; // 目标在有序的左半部分
} else {
left = mid + 1; // 目标在右半部分
}
} else { // 右半部分有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // 目标在有序的右半部分
} else {
right = mid – 1; // 目标在左半部分
}
}
}

return –1;
}

类型4：最优化问题（抽象二分）

// 问题：在 D 天内送达包裹的能力
int shipWithinDays(vector<int>& weights, int days) {
// 确定二分搜索边界
int left = *max_element(weights.begin(), weights.end()); // 最小能力
int right = accumulate(weights.begin(), weights.end(), 0); // 最大能力

while (left < right) {
int mid = left + (right – left) / 2;

if (canShip(weights, days, mid)) {
right = mid; // 尝试更小的能力
} else {
left = mid + 1; // 需要更大的能力
}
}

return left;
}

bool canShip(vector<int>& weights, int days, int capacity) {
int current = 0, needed = 1;

for (int weight : weights) {
if (current + weight > capacity) {
needed++;
current = 0;
}
current += weight;
}

return needed <= days;
}

🚀 教学要点

给初学者的建议

二分查找的思维转换

练习题进阶路径

Level 1: 基础二分查找（704题）
Level 2: 寻找边界（34题）
Level 3: 旋转数组搜索（33、81题）
Level 4: 抽象二分查找（875、1011题）
Level 5: 二维二分查找（74、240题）
Level 6: 复杂最优化问题（410、1231题）

📝 一句话总结各类问题

🎁 终极心法

二分查找 = 有序数据 + 折半排除 + 边界处理

四步解题法

调试技巧

// 在循环中添加打印，观察搜索过程
while (left <= right) {
int mid = left + (right – left) / 2;
cout << "left=" << left << ", right=" << right
<< ", mid=" << mid << ", nums[mid]=" << nums[mid] << endl;
// …
}

掌握二分查找的关键在于理解其"减而治之"的思想，并通过大量练习熟悉各种变体。从标准二分开始，逐步挑战更复杂的问题，最终能够灵活运用二分思想解决各类最优化问题。