Java binary search: lower bounds and duplicate values

Define the required result

A membership query can return any matching index. A report that groups duplicate values needs the first matching position. A lower-bound search returns the first position whose value is not less than the target, including the insertion position when the target is absent.

The program keeps a half-open interval [low, high). Initially low is zero and high is the array length. An empty array is therefore a valid input with an empty interval, and the result is zero.

When the middle value is below the target, all earlier values are also below it under the sorting precondition. Otherwise the middle position remains a candidate and the upper bound moves to it. This invariant is what makes narrowing correct, not merely the use of a while loop.

Avoid an overflowing midpoint

low + (high - low) / 2 avoids adding two possibly large positive indices. It also makes the half-open interval arithmetic easy to check. Search bounds are positions, so the returned length value is not a readable element index.

Arrays.binarySearch uses a different absent-value convention: its negative result encodes the insertion point. With duplicate matching values, it does not promise the first one. Translate that return contract instead of assuming the custom lower-bound result is interchangeable.

Never run this algorithm over unsorted values and interpret a plausible answer as success. If the batch must be sorted first, include that sorting cost in the whole operation.

Working program

public class ShipmentThresholdSearch {
    static int lowerBound(int[] thresholds, int target) {
        int low = 0;
        int high = thresholds.length;
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (thresholds[middle] < target) low = middle + 1;
            else high = middle;
        }
        return low;
    }
    public static void main(String[] args) {
        int[] thresholds = {10, 20, 20, 35, 80};
        System.out.println(lowerBound(thresholds, 20));
        System.out.println(lowerBound(thresholds, 22));
        System.out.println(lowerBound(thresholds, 90));
        System.out.println(lowerBound(new int[0], 20));
    }
}

Output

1
3
5
0

Cost and design choices

Each iteration roughly halves the candidate interval, so an already sorted array needs O(log n) comparisons and O(1) extra state. Array indexing is O(1), which is part of this cost argument.

Applying index-based searching to a linked list adds traversal work at each indexed access. A logarithmic comparison count alone does not guarantee logarithmic total work on a sequential-access structure.

For one lookup in an unsorted small array, linear search may cost less than sorting first. Binary search becomes useful when the ordering already exists or many queries share a sorted dataset.

Common Mistakes

• Do not read array[result] when result equals array.length.
• Do not mix inclusive and exclusive bound formulas.
• Do not assume a duplicate match is the first match.
• Test empty input, all-smaller input, all-larger input, and duplicate runs.

Connect the contracts

Compare the boundary explained in Array bounds with the assumptions made by this program.

Compare the Python boundary

Python binary search: use a half-open interval and require sorted input.