Lower Bound

Given a sorted array of n integers and an integer x, find the lower bound of x — the smallest index i where arr[i] >= x. If it doesn’t exist, return n.

Brute force (linear search, O(n)):

public static int lowerBound(int[] arr, int n, int x){
    for(int i = 0; i < n; i++){
        if(arr[i] >= x){
            return i; // lower bound found
        }
    }
    return n;
}

Optimal (binary search, O(log n)): place low at the first index and high at the last. Compute mid. If arr[mid] >= x, mid might be the answer — record it in ans and search the left half (high = mid - 1). Otherwise, mid is too small — search the right half (low = mid + 1). Continue until low crosses high.

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

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

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