1.说明

前面介绍了二分查找代码框架,
查找的都是与target相同的数，
本文介绍的二分查找变体，
查找的是正好大于或者小于target的数，
即要找的数target不存在，
希望返回满足一定要求的数。

2.查找正好大于target的元素

这是二分查找代码框架中,
查找左侧边界代码框架的变体，
当target不存在时，
得到的索引恰好是比target大的最小元素的索引，
即nums数组中第1个大于target的元素索引。

public static int leftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    // 下面的两个判断可省略，最终结果会覆盖这两种情况
    // target比最小的元素还小，那索引为0的元素正好比target大
    if (target < nums[left]) {
        return 0;
    }
    // target比最大的元素还大，则-1表示没有比target大的元素了
    if (target > nums[right]) {
        return -1;
    }
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 不能返回，锁定左边界，继续缩小右边界
            right = mid - 1;
        }
        // 上面的"right = mid - 1;"代码体相同，
        // 判断条件可以合并为else if (nums[mid] >= target)
    }
    return left;
}

3.查找正好小于target的元素

这是二分查找代码框架中,
查找右侧边界代码框架的变体,
当target不存在时，
得到的索引恰好是比target小的最大元素的索引，
即nums数组中最后一个小于target的元素索引。

public static int rightBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    // 下面的两个判断可省略，最终结果会覆盖这两种情况
    // target比最小的元素还小，则-1表示没有比target小的元素了
    if (target < nums[left]) {
        return -1;
    }
    // target比最大的元素还大，那索引为nums.length-1的元素正好比target小
    if (target > nums[right]) {
        return right;
    }
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 不能返回，锁定右边界，继续缩小左边界
            left = mid + 1;
        }
        // 上面的"left = mid + 1;"代码体相同，
        // 判断条件可以合并为else if (nums[mid] <= target)
    }
    return right;
}

4.二分查找（变体）代码框架优化

如下代码优化后非常简洁，
适合在实际项目中使用，
但是不推荐记忆下面的代码框架，
因为合并了很多实现细节，
不利于分析和理解，
还是推荐记忆上面的原始版本。

4.1.查找左侧边界变体优化

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

4.2.查找右侧边界变体优化

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