二分查找

查找第一个不小于目标的元素

给定非降序的 int 数组 a，求第一个满足 a[i] >= target 的下标 i。不存在时返回数组长度 n，这也是保持顺序的插入位置。遇到相等值时，仍需继续向左找。

用 [left, right) 表示待检查区间，初始为 left=0、right=n。left 指向第一个待检查元素，right 指向区间之后的位置。区间长度是 right-left，为零时查找结束。

返回值可能是 n，判断目标是否存在时，需要检查 i<n 与 a[i]==target。空数组返回零。

传入数组应为非空引用，已排序且在查找期间保持不变。

怎样缩小区间

循环始终保持 0 <= left <= right <= n，left 左边的元素都小于 target，从 right 开始的元素都大于等于 target。初始时这两块区域为空，整个数组都待检查。

当 left<right 时，取 mid=left+(right-left)/2。若 a[mid]<target，从 left 到 mid 都小于目标，可令 left=mid+1。

若 a[mid]>=target，mid 及其右边都不小于目标，令 right=mid。虽然 mid 可能是答案，但它已确定满足条件，接下来只需检查它左边的元素。

两个分支都会缩短 right-left。即使只剩一个元素，也会推进一个端点，最终使区间长度变为零。

结束时 left=right，该位置之前的元素都小于目标，从该位置起的元素都不小于目标，所以 left 就是答案。

Java 实现

public class LowerBound {
    static int lowerBound(int[] a, int target) {
        int left = 0, right = a.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (a[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 3, 7};
        int i = lowerBound(a, 3);
        System.out.println(i); // 1
        System.out.println(i < a.length && a[i] == 3); // true
    }
}

示例可保存为 LowerBound.java 并运行。中点表达式先计算区间差值，避免直接相加两端下标的溢出风险。循环只在非空区间内读取 a[mid]，因此 right=n 不会导致读取 a[n]。

查找目标 3 时，两次相等判断把右端缩到 2 和 1，最后 a[0]<3，把左端推进到 1，得到重复段的起点。

这里不能把小于分支改成 left=mid，否则单元素区间可能不再收缩。也不能把另一分支改成 right=mid-1，否则会跳过尚未判定的元素。

边界与复杂度

这些用例覆盖空数组、单元素、重复值，以及目标落在元素间或数组两端之外的情况。还可以随机生成短有序数组，用线性扫描的结果核对二分查找。

如果要找第一个严格大于目标的位置，将小于分支的条件改成 a[mid]<=target。这样左侧元素都小于等于目标，右侧元素都严格大于目标。这个上界与 lower_bound 的下标差就是目标出现次数。

每次迭代把待查区间缩小到约一半，时间复杂度为 O(log n)，额外空间为 O(1)。找到位置后向普通数组插入元素，移动后缀仍可能需要 O(n) 时间。

二分也可用于其他单调条件：按顺序先是一段不满足条件的位置，再是一段满足条件的位置，就能查找两段的交界。