登录以参加训练计划

二分查找

二分查找基本思想

二分查找是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

二分查找边界

int binary_search(int l, int r, int target) {
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return r; // 或 return l
}

最大化最小值 / 最小化最大值

当题目要求"最大化最小距离"或"最小化最大时间"时，通常使用二分答案的方法：

1. 确定答案的范围 [l, r]
2. 使用二分查找寻找最优解
3. 每次取中点 mid，判断是否满足条件
4. 根据判断结果调整搜索范围