面试算法：二分查找

二分查找的难点不是思想，而是边界。

左闭右开模板

int l = 0, r = nums.size();
while (l < r) {
    int mid = l + (r - l) / 2;
    if (nums[mid] < target) {
        l = mid + 1;
    } else {
        r = mid;
    }
}

结束时 l == r。

答案二分

当问题具有单调性，但不是直接在数组里找值时，可以二分答案。

例如最小速度、最大容量、最小天数。

我更喜欢统一成 lower_bound

很多二分题本质上是在找第一个满足条件的位置。把问题统一成这个模型后，模板会稳定很多：

while (l < r) {
    int mid = l + (r - l) / 2;
    if (ok(mid)) {
        r = mid;
    } else {
        l = mid + 1;
    }
}

循环结束时，l 就是第一个满足 ok 的位置。

二分答案的判断函数

答案二分最重要的是 ok(mid)。它必须具备单调性：如果某个答案可行，那么更大或更小的一侧也应该全部可行。

比如“运货最小容量”：容量越大越容易完成，所以 ok(capacity) 是单调的。

常见坑

mid = (l + r) / 2 可能溢出，推荐写成 l + (r - l) / 2。虽然很多题数据范围不大，但养成习惯更好。