A login service keeps a sorted array of active session IDs and, on every request, walks it from index 0 looking for sessionId. The list is already ordered. The check still costs a linear scan. Nobody “wrote a bad array.” They ran the wrong procedure on a layout that already allowed cutting the remaining range in half.

Binary search is a procedure that requires a sorted invariant; each step discards half the remaining range. Membership, first occurrence, and insertion point are the same loop with a different stop condition. The sort is the license to discard, not decoration.

This post is the procedure. Families, Big-O literacy, and ADT vs implementation live on the Algorithms Roadmap. Here we only care about a sorted range, the loop that shrinks it, and what Java encodes when the key is missing.

The invariant: the answer, if any, is still in [lo, hi]

Pick inclusive bounds and keep them for membership: lo and hi are valid indices, and the live range is a[lo] .. a[hi]. After every comparison two facts stay true:

  1. a[lo] .. a[hi] is still sorted (it was a slice of a sorted array).
  2. If the target exists in the original array, it still exists in that slice.

That is the whole license. When a[mid] < target, every index <= mid is too small, so lo = mid + 1. When a[mid] > target, every index >= mid is too large, so hi = mid - 1. You never look at a discarded half again.

If the array is not sorted, those implications are lies. You can still pick a mid and return some index or -1. That return is not a search result; it is a coin flip dressed as a loop.

Note: The invariant is about the remaining range, not “sorted at allocation.” Insert, delete, or overwrite without restoring order and the next binary search is undefined.

A walked pass: find 24

Seven IDs, already ordered. Target is 24. Inclusive lo / hi. Mid is lo + (hi - lo) / 2 — not (lo + hi) / 2, so a large int index cannot overflow into a negative mid.

a = [3, 8, 12, 19, 24, 31, 45]
     0  1   2   3   4   5   6

hit 24:
  lo=0 hi=6 mid=3  a[3]=19  19<24  → lo=4
  lo=4 hi=6 mid=5  a[5]=31  31>24  → hi=4
  lo=4 hi=4 mid=4  a[4]=24  found at 4

miss 20:
  lo=0 hi=6 mid=3  a[3]=19  19<20  → lo=4
  lo=4 hi=6 mid=5  a[5]=31  31>20  → hi=4
  lo=4 hi=4 mid=4  a[4]=24  24>20  → hi=3
  lo=4 hi=3  empty — 20 is not present; insertion point is lo=4

Three comparisons for seven slots; linear scan would have taken five here, and n when the ID is missing or last. Each step threw away half of what was left. lo > hi means the invariant has nothing left to protect. The insertion point — where 20 would go to keep the array sorted — is lo.

The loop: inclusive lo / hi

The membership sketch that matches the walk. Stay on inclusive bounds; do not mix in a half-open hi halfway through a method.

static int indexOf(long[] sortedIds, long target) {
    int lo = 0;
    int hi = sortedIds.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        long v = sortedIds[mid];
        if (v == target) {
            return mid;
        }
        if (v < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

boolean isActive(long[] sortedIds, long sessionId) {
    return indexOf(sortedIds, sessionId) >= 0;
}

lo <= hi is the inclusive test: one remaining slot is still a legal range. On exit, lo is the insertion point and hi is lo - 1. That pair is how lower bound, upper bound, and Arrays.binarySearch’s miss encoding all fall out of one idea. Same layout as contains. Different procedure.

Lower bound: first index that is not less than the key

Membership is “is it here?” Production often asks “where would it sit?” Lower bound is the first index i such that a[i] >= target. If every element is smaller, it is a.length.

Duplicates make this the version you want. Session IDs should be unique; event timestamps and sorted scores are not. indexOf returns an equal index, not necessarily the leftmost. Do not return on equality: an earlier twin may still sit to the left, so you shrink hi.

static int lowerBound(long[] a, long target) {
    int lo = 0;
    int hi = a.length; // exclusive: answer may be a.length
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

This section uses half-open [lo, hi) on purpose: the answer is an insertion index in 0 .. a.length, not only a hit inside the array. Do not copy hi = a.length into indexOf. Inclusive membership (hi = n - 1) and lower bound (hi = n) are two contracts. Mixing them is how you read a[a.length].

On [3, 8, 12, 19, 24, 24, 24, 31], lowerBound(a, 24) is 4. lowerBound(a, 20) is 4 as well — first slot not less than 20. lowerBound(a, 45) is 8, past the last element.

Lower bound answers “first not-less-than” whether the key exists or not. Count of copies of k is upperBound(a, k) - lowerBound(a, k).

Upper bound: first index strictly greater than the key

Upper bound is the first index i such that a[i] > target. Same half-open range, one comparison flipped: equality still belongs on the left, so you advance lo.

static int upperBound(long[] a, long target) {
    int lo = 0;
    int hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

Same array, upperBound(a, 24) is 7 (the 31). The three 24s occupy [lowerBound, upperBound) = [4, 7). An absent key still has a well-defined bound: upperBound(a, 20) is 4, same as lower bound, so occupancy is empty. Membership returns on equality; lower bound treats equality as “keep looking left”; upper bound treats it as “keep looking right.”

Off-by-one: infinite loop and the last slot

The failure mode is not “forgot the formula.” It is a range that does not shrink, or a range that shrinks past the last candidate.

Infinite loop. Inclusive while (lo <= hi) with hi = mid instead of hi = mid - 1: when lo == hi, mid stays lo and the loop never ends. Inclusive bounds must drop mid on every unequal branch (lo = mid + 1 or hi = mid - 1). Half-open lower/upper bound may set hi = mid because mid is still a legal answer and lo < hi still makes progress.

Missed last element. while (lo < hi) with hi = n - 1 never inspects index n - 1. The last session ID is the one you skip. Inclusive membership uses hi = n - 1 and lo <= hi. Half-open bound uses hi = n and lo < hi. Pick one pair per method and write it at the top.

Overflow mid. (lo + hi) / 2 overflows when the sum exceeds Integer.MAX_VALUE; mid goes negative and a[mid] throws. lo + (hi - lo) / 2 stays in range if lo and hi were already valid.

Note: Off-by-one bugs pass a test that only hits the middle. Probe the first slot, the last slot, an absent key just below a[0], and an absent key just above a[n - 1].

What Arrays.binarySearch returns on a miss

Do not hand-roll membership in production if the JDK already has the loop. On a sorted long[], Arrays.binarySearch returns the index when the key is present. When the key is absent it does not return -1.

It returns -(insertionPoint) - 1. insertionPoint is the index of the first element greater than the key, or a.length if every element is smaller — the same number lowerBound returned for a missing key.

long[] ids = {3, 8, 12, 19, 24, 31, 45};

int hit = Arrays.binarySearch(ids, 24L);  // 4
int miss = Arrays.binarySearch(ids, 20L); // -5
int ins = -miss - 1;                      // 4 — 20 would insert at index 4

boolean contains(long[] sortedIds, long id) {
    return Arrays.binarySearch(sortedIds, id) >= 0;
}

-5 is not a mysterious error code. Solve result = -(insertionPoint) - 1: insertionPoint = -result - 1. The bitwise complement ~result is the same value. After a miss you can insert at that index and the array stays sorted.

Any negative means “not found” for a boolean contains. Treating -1 as the only miss, or using a negative return as an index, is how a missing session becomes ArrayIndexOutOfBoundsException or a silent wrong slot.

Duplicates: Arrays.binarySearch does not promise the leftmost equal key. If you need first or last occurrence, use the bound loops above. The JDK method is a membership-and-insertion-point primitive, not a multi-set API.

Not a reason to sort on every lookup

Binary search does not make an unordered array cheap. Sorting so that one lookup is “legal” pays O(n log n) to avoid an O(n) scan. You lost.

Do not sort on every lookup to make binary search legal. Sort once when the set is built, or keep the array ordered as you insert (binary search for the insertion point, then slide — that bill is the array’s, not this procedure’s). If inserts and lookups are both hot, this layout is the wrong default; a tree or a hash set is a different job.

The login table rebuilt once a minute and then queried a hundred thousand times is this job: one sort (or an already-ordered extract), then O(log n) per request. Sorting inside isActive on every write is cargo-cult of the name.

Complexity

The procedure does not allocate and does not rearrange. “In-place” here means it does not mutate. Stability is a sort property. It does not apply.

TimeO(log n) comparisons in the worst case
Extra space (iterative)O(1)
StableN/A (not a sort)
In-placeYes — reads only; does not mutate

Worst case is a miss, or a hit in the last remaining slot: about log₂ n probes. Compare to the linear contains the login service was running: O(n) time, also O(1) extra space. Same layout, different bill — the roadmap contrast.

Skip it when:

  • The data is not sorted. The loop will compile. The answer is not meaningful. Sort once, or pick a hash set.
  • n is tiny and the scan is the clearer code. A five-element config table does not need a hand-rolled bound loop. Linear is honest. The JDK call is still fine if the array is already sorted and you want one line.
  • Callers mutate the array and nobody re-establishes order. An isActive that binary-searches after sortedIds[i] = newId is a latent production bug. Restore the invariant or stop calling this procedure.

Binary search is for a range that is already ordered and will stay ordered for the reads you are about to do.

JDK: Arrays.binarySearch and Collections.binarySearch

The hub’s default: sorted lookup → Arrays.binarySearch (or Collections.binarySearch on a sorted List). Call it unless you need leftmost/rightmost among duplicates, or a custom bound the JDK does not expose.

int[] primitive = {3, 8, 12, 19, 24};
int p = Arrays.binarySearch(primitive, 12);          // 2

List<String> names = List.of("ann", "bea", "cy", "drew");
int i = Collections.binarySearch(names, "cy");       // 2

Arrays.binarySearch overloads cover every primitive array, Object[] with natural order, and Object[] plus a Comparator. Range overloads take fromIndex / toIndex (half-open) and search only that slice — useful when the live prefix of a capacity array is sorted and the tail is garbage.

Collections.binarySearch needs a List sorted in the comparator you pass (or natural order). On an ArrayList it is the same O(log n) indexed loop. On a LinkedList each mid is a linear walk — a layout mistake, not a reason to avoid the name.

Note: Neither method verifies that the data is sorted. An unsorted input is not an exception. It is a wrong answer.

Hand-roll the bound loops when you need lower/upper bound or a count of duplicates. Do not hand-roll membership on the login path; the JDK already encodes the miss.

Cheat sheet

Invariant:    remaining [lo, hi] is sorted; answer, if any, is inside it
Each step:    discard the half that cannot contain the target
Membership:   inclusive lo/hi, return on equal, else drop mid
Lower bound:  first i with a[i] >= key  (half-open hi = n)
Upper bound:  first i with a[i] >  key
Miss (JDK):   Arrays.binarySearch → -(insertionPoint) - 1
Time:         O(log n)     extra space: O(1) iterative
Do not:       sort on every lookup; search an unsorted range
JDK:          Arrays.binarySearch / Collections.binarySearch

Do:

  • Check the sorted invariant before you call the loop or the JDK method.
  • Use lo + (hi - lo) / 2, and probe first, last, and both miss sides in tests.
  • Decode a negative Arrays.binarySearch result as an insertion point, not as -1.

Don’t:

  • Sort on every lookup so the name “binary search” applies.
  • Mix inclusive hi = n - 1 with half-open while (lo < hi) in the same method.
  • Assume Arrays.binarySearch returns the leftmost duplicate, or -1 on a miss.

Wrap-up

Binary search is not a clever index formula. It is a procedure that is legal only while the remaining range is sorted and still contains the answer, if the answer exists. Each comparison throws away half of that range. Lower and upper bound are the same idea with a different half-discard rule. Arrays.binarySearch already implements membership and encodes a miss as -(insertionPoint) - 1.

Use it when the login table is already ordered and will stay ordered. Use the JDK call for contains and insert-at. Hand-roll bounds when duplicates are the job. When the data is unsorted, tiny, or mutated without repair, this procedure is the wrong bill — pick the match from the Algorithms Roadmap.

Next optional step in the series One pass from both ends when nested loops are the bill. Two Pointers: One Pass From Both Ends