lowerBound方法

lowerBound方法在数组arr中寻找第一个大于等于（不小于）target的元素的位置。

如果数组中存在target，它会返回第一个target出现的位置；

如果不存在，它会返回第一个大于target的元素的位置。

如果数组中的所有元素都小于target，那么它将返回数组的长度，表示target应该被插入到数组的末尾。

初始化

设置两个指针l和r，分别指向数组的起始位置和结束位置。即l = 0，r = arr.length - 1。

循环不变量

循环不变量指在循环的每次迭代之前、之后以及循环结束时都保持为真的性质或条件。

始终保持以下循环不变量：

• 如果目标位置存在于数组arr中，那么它一定在当前查找区间[l, r]内。
• (-∞, l-1]一定小于target，[r+1, +∞]一定大于等于target。

维护

在循环的每一步中，计算中间位置mid = l + (r - l) / 2。

比较arr[mid]与target的值：

• 如果arr[mid] == target，则更新r指针，使其指向mid - 1，这样我们可以在左侧继续寻找第一个target。
• 如果arr[mid] > target，则更新r指针，使其指向mid - 1，因为target只能在左侧区间。
• 如果arr[mid] < target，则更新l指针，使其指向mid + 1，因为target只能在右侧区间。

终止

循环终止的条件是l大于r，即l - 1 = r 。此时，循环不变量帮助我们得出最终结果：

• 当循环结束时，如果target存在于数组中，那么它一定在[l, r]区间内。但由于l大于r，区间为空，相当于遍历完全所有可能结果，这意味着我们找到了target或者确定了target应该插入的位置。

• 根据循环不变量：(-∞, l-1]一定小于target，[r+1, +∞]一定大于等于target。

  得出此时l不满足小于target，r不满足大于等于target，r+1为第一个大于等于target的位置，又因为l - 1 = r ，则l可以作为结果。

因此，当循环结束时，l就是我们要找的位置，可以直接返回l作为结果。

查看代码

public int lowerBound(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] > target) {
            r = mid - 1;
        } else if (arr[mid] < target) {
            l = mid + 1;
        } else {
            r = mid - 1; // 当找到target时，继续在左侧寻找第一个target
        }
    }
    return l;
}