I Lower Bound

Problem

You are given an array 'arr' sorted in non-decreasing order and a number 'x'.

You must return the index of lower bound of 'x'. (link)

Note:

For a sorted array 'arr', 'lower_bound' of a number 'x' is defined as the smallest index 'idx' such that the value 'arr[idx]' is not less than 'x'

If all numbers are smaller than 'x', then 'n' should be the 'lower_bound' of 'x', where 'n' is the size of array. Consider 0-based indexing.

Example:

Input: ‘arr’ = [1, 2, 2, 3] and 'x' = 0

Output: 0

Explanation: Index '0' is the smallest index such that 'arr[0]' is not less than 'x'.

Solution

We utilize the standard binary search method. If we discover that the midpoint is greater than the target element 'x', we store its index as a potential answer. Ultimately, the 'answer' variable will hold the smallest index that is greater than or equal to the target 'x'.

public class Solution {
    public static int lowerBound(int []arr, int n, int x) {
        int low = 0;
        int high = arr.length-1;

        int ans = arr.length;

        while(low<=high){
            int mid = (low+high)/2;

            if(x<=arr[mid]){
                ans = mid;
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }
        return ans;
    }
}

II Upper Bound

Problem

You are given a sorted array ‘arr’ containing ‘n’ integers and an integer ‘x’.

Implement the ‘upperBound’ function to find the index of the upper bound of 'x' in the array. (link)

Note: The upper bound in a sorted array is the index of the first value that is greater than a given value. If the greater value does not exist then the answer is 'n', Where 'n' is the size of the array. We are using 0-based indexing. Try to write a solution that runs in log(n) time complexity.

Example:

Input : ‘arr’ = {2,4,6,7} and ‘x’ = 5,
Output: 2

Explanation: The upper bound of 5 is 6 in the given array, which is at index 2 (0-indexed).

Solution

This mirrors the concept of a lower bound, with the distinction that we omit the equality case check. In essence, both lower bound and upper bound are variations of the upper bound concept.

public class Solution {
    public static int upperBound(int []arr, int x, int n){

        int low = 0;
        int high = arr.length - 1;

        int ans = arr.length;

        while(low<=high){
            int mid = (low+high)/2;

            if(x<arr[mid]){
                ans = mid;
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }

        return ans;
    }
}

III Application of Lower Bound

Search and Insert

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity. (link)

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Solution

Same as Lower Bound problem.

IV Floor and Ceil

Problem

You're given a sorted array 'a' of 'n' integers and an integer 'x'.

Find the floor and ceiling of 'x' in 'a[0..n-1]'. (link)

Note:

Floor of 'x' is the largest element in the array which is smaller than or equal to 'x'. Ceiling of 'x' is the smallest element in the array greater than or equal to 'x'.

Example:

Input: 
n=6, x=5, a=[3, 4, 7, 8, 8, 10]   

Output:
4

Explanation:
The floor and ceiling of 'x' = 5 are 4 and 7, respectively.

Solution

Directly use the standard binary search template. If the target is greater than mid than store in ceil else store it in floor.

public class Solution {
    public static int[] getFloorAndCeil(int[] a, int n, int x) {
        int low = 0;
        int high = a.length-1;
        int floor = -1;
        int ceil = -1;

        while(low<=high){
            int mid = (low+high)/2;

            if(x==a[mid]){
                return new int[]{x,x};
            }

            if(x<a[mid]){
                ceil = a[mid];
                high = mid - 1;
            }
            else{
                floor = a[mid];
                low = mid + 1;
            }
        }

        return new int[]{floor, ceil};
    }

}