Java实现 lower_bound() 和 upper_bound()

在Java中，可以使用二分查找来实现lower_bound()和upper_bound()函数。

下面是lower_bound()函数的实现：

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

下面是upper_bound()函数的实现：

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

其中，lower_bound()函数返回第一个大于等于target的元素的下标，如果不存在，则返回arr.length；upper_bound()函数返回第一个大于target的元素的下标，如果不存在，则返回arr.length。

需要注意的是，这两个函数的前提是数组arr已经按升序排好序。如果数组arr是降序排列，则需要将if条件判断语句中的">="和"<="互换。