左边界

一句话理解

左边界：第一个 >=x 的位置。

为什么要学

有重复值时找最左边那个。

讲解

找到 a[mid]>=x 时记下并往左缩。相当于 lower_bound。

要分清“第一个真的等于 x”和“第一个大于等于 x”。

例子

while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] >= x) { ans = mid; r = mid - 1; }
    else l = mid + 1;
}

能满足就尝试更左。

常见错误

• 找到等于就立刻返回，得到的不是最左。
• ans 未初始化。