Implement Lower Bound

The lower bound of a number x in a sorted array arr is the smallest index idx such that arr[idx] >= x. If all elements in the array are less than x, the lower bound is n (the size of the array).
If all numbers are smaller than x, then n should be the lower_bound of x, where n is the size of the given array.

Example 1

Input:
arr = [1, 3, 5, 7, 9]
x = 6

Output:
Lower bound of 6 is at index 3

Example 2

Input:
arr = [2, 4, 6, 8, 10]
x = 12

Output:
Lower bound of 12 is at index 5

Code

public class Solution {
    public static int lowerBound(int[] arr, int x) {
        int lb = arr.length;
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) / 2);
            if (arr[mid] >= x) {
                lb = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return lb;
    }
}

• Time Complexity: O(log N), where N is the size of the given array.
• Space Complexity: O(1) as we are using no extra space.

Implement Upper Bound

The upper bound of a number x in a sorted array arr is the smallest index idx such that arr[idx] > x. If all elements in the array are less than or equal to x, the upper bound is n (the size of the array).
If the greater value does not exist then our answer is n, Where n is the size of the given array.

Example 1

Input:
arr = [1, 2, 4, 6, 8]
x = 5

Output:
Upper bound of 5 is at index 3

Example 2

Input:
arr = [1, 3, 5, 7, 9]
x = 2

Output:
Upper bound of 2 is at index 1

Code

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

• Time Complexity: O(log N), where N is the size of the given array.
• Space Complexity: O(1) as we are using no extra space.