☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Lower Bound

Easy TUF ID 80 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array arr sorted in non-decreasing order (duplicates allowed) and an integer x. The lower bound of x is the smallest index i such that arr[i] >= x. If no such element exists, every value is smaller than x and the answer is n, the length of the array. In other words, the lower bound is the position where x would be inserted to keep the array sorted, placing it before any existing copies of x.

Constraints: 0 ≤ n ≤ 10^5, values and x fit in a 32-bit signed integer.

Example 1

arr = [1, 2, 2, 3, 3, 5], x = 2
answer = 1                // arr[1] is the first element >= 2

Example 2

arr = [1, 2, 2, 3, 3, 5], x = 4
answer = 5                // 4 is absent; arr[5] = 5 is the first element >= 4

Example 3

arr = [1, 2, 2, 3, 3, 5], x = 6
answer = 6                // every element is < 6, so return n

This is the function that C++ calls std::lower_bound. Java’s Arrays.binarySearch does not return it directly, which is why it is worth knowing how to write by hand.

Approach 1: Brute force, linear scan

Intuition. Walk from left to right and stop at the first element that is >= x. Since values never decrease, the first such position is the smallest index that qualifies, exactly what the definition asks for. If we fall off the end, nothing qualified, so return n.

Algorithm.

  1. For every index i from 0 to n - 1: if arr[i] >= x, return i.
  2. Return n.
static int bruteForce(int[] arr, int x) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] >= x) return i;
    }
    return arr.length;
}

Complexity. Time O(n): one pass in the worst case (when x exceeds everything). Space O(1).

Approach 2: Optimal, binary search with a running answer

Intuition. Look at the predicate arr[i] >= x across the sorted array. It is false for a prefix and true for the rest, so the array looks like F F F ... F T T ... T. The lower bound is the index of the first T. A monotone predicate like this is exactly what binary search is for: probe the middle; if it is T, the first T is here or further left; if it is F, the first T is strictly to the right.

We keep a variable ans, initialised to n (the answer when there is no T at all). Every time we see a T at mid we record it as the best answer so far and continue searching to the left for an even smaller qualifying index. Every time we see an F we move right. When the range empties, ans is the smallest index that was ever a T, which is the first T.

Algorithm.

  1. Set lo = 0, hi = n - 1, ans = n.
  2. While lo <= hi:
    • mid = lo + (hi - lo) / 2.
    • If arr[mid] >= x: set ans = mid and hi = mid - 1.
    • Else set lo = mid + 1.
  3. Return ans.
static int optimal(int[] arr, int x) {
    int lo = 0, hi = arr.length - 1, ans = arr.length;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= x) {
            ans = mid;            // mid qualifies; a smaller qualifying index may exist on the left
            hi = mid - 1;
        } else {
            lo = mid + 1;         // arr[mid] < x, so every index <= mid is too small
        }
    }
    return ans;
}

Dry run on arr = [1, 2, 2, 3, 3, 5], x = 2:

lo hi mid arr[mid] arr[mid] >= 2? action
0 5 2 2 yes ans = 2, hi = 1
0 1 0 1 no lo = 1
1 1 1 2 yes ans = 1, hi = 0
1 0     lo > hi return 1

Notice how ans moved from 2 to 1: finding a qualifying index is not enough, we keep narrowing until the smallest is confirmed.

Complexity. Time O(log n): the range halves each iteration. Space O(1).

Why does this find the first T and not just any T? Whenever ans is set to mid, the search continues only in [lo, mid - 1], so any later ans is strictly smaller. And whenever we skip left of a position (lo = mid + 1), that position and everything before it was an F, so nothing qualifying was discarded. Together these mean the final ans is the leftmost T.

Approach 3: Optimal, half-open range without an ans variable

Intuition. A second popular template keeps the candidate range as a half-open interval [lo, hi) and maintains a tighter invariant: the answer is always inside [lo, hi]. We start with lo = 0, hi = n, because the answer can be any index from 0 up to and including n. If arr[mid] >= x, then mid might be the answer, so we set hi = mid and keep it. If arr[mid] < x, mid cannot be the answer, so lo = mid + 1. The loop stops when lo == hi, and that single remaining value is the answer. There is no separate ans to maintain and no risk of forgetting to update it.

Algorithm.

  1. Set lo = 0, hi = n.
  2. While lo < hi:
    • mid = lo + (hi - lo) / 2.
    • If arr[mid] >= x, set hi = mid; else set lo = mid + 1.
  3. Return lo.
static int optimalHalfOpen(int[] arr, int x) {
    int lo = 0, hi = arr.length;      // invariant: the answer lies in [lo, hi]
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= x) hi = mid;  // mid itself may be the answer, so keep it inside the range
        else lo = mid + 1;            // mid is too small, so exclude it
    }
    return lo;
}

Complexity. Time O(log n), space O(1).

Two details make this loop safe. First, mid is always strictly less than hi because lo < hi implies mid <= (lo + hi - 1) / 2 < hi, so arr[mid] is never read at index n. Second, the loop always progresses: either hi shrinks to mid < hi or lo grows to mid + 1 > lo. When the loop exits lo == hi, and the invariant says the answer is in [lo, hi], so it is lo.

Both templates are correct; pick one and use it consistently. The ans version reads more like “search and remember”; the half-open version is shorter and generalises nicely to “find the first index where a predicate becomes true”.

Edge cases and pitfalls