二分查找算法的思路

二分查找思路总结

1. 明确目标与单调性特点：

   • 核心目标：寻找满足某种条件的答案（如最小/最大值）。
   • 单调性要求：需要证明你的判断函数具有单调性——即如果某个答案 T 可行，那么大于 T 的答案通常也是可行的；反之，如果 T 不可行，那么小于 T 的答案也一定不可行。
   • 笔记要点：问题必须具有“阈值”性质，才能通过不断试探、缩小范围来逼近最优解。

2. 设计边界（取值区间）：

   • 下界的设计：
     根据问题的最苛刻条件得出最低可能值。例如在任务分配问题中，每个任务必须独立完成，所以最小时间至少是所有任务里最大单个任务的时间。
   • 上界的设计：
     提供一个肯定可行的最坏情况。例如所有任务只能由一个人完成时，所需时间为任务总时间。
   • 笔记要点：边界的选择应基于问题的极限情况，确保区间内存在答案且边界足够紧凑。

3. 构建可行性（判断）函数：

   • 目的：给定一个候选答案 T，判断是否存在一种方案使问题条件（比如任务分配）满足。
   • 思考方法：模拟或验证该方案是否满足所有限制条件。
   • 笔记要点：可行性函数通常是问题求解的核心，它依据单调性确保二分过程中答案变化呈现明确趋势。

4. 二分搜索框架：

   • 基本流程：
     • 设定初始左右边界（low, high）；
     • 求候选值 mid = (low + high) / 2；
     • 如果 mid 对应的方案可行，那么尝试缩小上界（high = mid）；
     • 如果 mid 不可行，则需要增大下界（low = mid + 1）；
     • 重复直到 low 与 high 收敛，此时 low 就是最优答案。
   • 笔记要点：整个过程利用了单调性特点，通过不断收缩答案区间，最终确定最小（或最大）的可行解。
     代码：

#include <iostream>
using namespace std;// 二分查找函数
int binarySearch(int arr[], int size, int target) {int left = 0, right = size - 1;while (left <= right) {int mid = left + (right - left) / 2; // 避免溢出if (arr[mid] == target) return mid;  // 找到目标，返回索引else if (arr[mid] < target)left = mid + 1; // 目标在右侧elseright = mid - 1; // 目标在左侧}return -1; // 未找到
}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13}; // 已排序数组int size = sizeof(arr) / sizeof(arr[0]);int target = 7;int index = binarySearch(arr, size, target);if (index != -1)cout << "目标 " << target << " 在索引 " << index << endl;elsecout << "目标不存在" << endl;return 0;
}

5. 注意细节与边界条件：
   • 确定是否有特殊情况（例如输入为空或极值情况）需要单独处理。
   • 在计算 mid 时注意防止溢出（如使用 mid = low + (high - low) / 2）。

---

适用场景

• 调度与分配问题：如任务分配、负载均衡、工程项目调度等，常要求在有限资源（人力、时间、机器）下最优化任务完成时间。
• 切分与分割问题：例如“切割木板”、“切分数组”问题，寻找一个阈值使得某些条件满足。
• 优化型问题：例如求最优答案、最大化最小值或最小化最大值，通常具有答案服从单调性的特性。
• 其他问题：任何可以将答案确定为一个数值（或区间），并能构造“判断函数”来验证当前答案是否满足条件的问题。

---

小结

二分查找思想的精髓在于将问题看作一个连续的（或者可以离散逼近的）答案区间，通过设计合理的上下界，再利用具有单调性的可行性判断函数来二分逼近最终答案。这种 方法能够大幅优化问题求解时间，适用于大量具有“阈值”决策特征的问题。