Why does Arrays.binarySearch return a negative number when the value is missing?

The Answer

• Found: the method returns the index.
• Absent: it returns -(insertion point) - 1, where the insertion point is where the value would go to keep the array sorted.
• Recover it with int ip = -result - 1;. That is the whole decode.
• The - 1 exists to break a tie: without it, "belongs at index 0" and "found at index 0" would both be 0.
• The precondition is yours to honour. The array must already be sorted. On an unsorted array the result is undefined — not an exception, just a wrong answer, sometimes.
• If several elements match, which index you get is not specified.

Understand It

The logic is one invariant, held across the loop

Binary search is easier to get right if you stop thinking about it as "halve the array" and start thinking about the promise the loop keeps:

If the target is in the array at all, it is somewhere in a[lo..hi].

That sentence is true before the loop starts (the range is the whole array), and every iteration must leave it true. That is all. Everything else follows.

loop while lo <= hi:                      # the range is non-empty
    mid ← lo + (hi - lo) / 2

    if a[mid] == target:  return mid
    if a[mid] <  target:  lo ← mid + 1    # target can only be to the right
    else:                 hi ← mid - 1    # target can only be to the left

# the range is now empty, so the target was never there,
# and lo has come to rest at the insertion point
return -(lo + 1)

The two ± 1 steps are the load-bearing part. mid has just been tested and rejected, so leaving it inside the range would break the promise (the range would still contain something known not to be the target) and, worse, would let lo and hi stop moving — an infinite loop.

Watching the range collapse

int[] a = {2, 4, 6, 8, 10, 12, 14};

System.out.println("searching for 12:");
System.out.println("  result " + trace(a, 12));
System.out.println();
System.out.println("searching for 7:");
System.out.println("  result " + trace(a, 7));

searching for 12:
  lo=0 hi=6 mid=3 a[mid]=8
  lo=4 hi=6 mid=5 a[mid]=12
  result 5

searching for 7:
  lo=0 hi=6 mid=3 a[mid]=8
  lo=0 hi=2 mid=1 a[mid]=4
  lo=2 hi=2 mid=2 a[mid]=6
  lo=3 hi=2  -> crossed, not present
  result -4

Look at the failed search. When the loop gives up, lo is 3 — and 3 is exactly where 7 belongs, between 6 and 8. That is not a coincidence and it is not extra work: lo only ever moves past values smaller than the target, so when the range empties, lo is sitting at the first value larger than the target. The insertion point falls out of the algorithm for free.

Returning -1 would throw that away and make the caller search again.

Why lo + (hi - lo) / 2 and not (lo + hi) / 2

They are the same number right up to the point where they are not. lo + hi is an int addition, and two large indices overflow it:

int lo = 1_500_000_000, hi = 2_000_000_000;

System.out.println("lo+hi overflows to : " + (lo + hi));
System.out.println("buggy mid          : " + (lo + hi) / 2);
System.out.println("safe  mid          : " + (lo + (hi - lo) / 2));

lo+hi overflows to : -794967296
buggy mid          : -397483648
safe  mid          : 1750000000

A negative mid means ArrayIndexOutOfBoundsException. This bug sat in the JDK's own Arrays.binarySearch for nine years and in Jon Bentley's Programming Pearls for twenty, which is the best evidence available that "obviously correct" and "correct" are different things. hi - lo cannot overflow because it is a difference of two non-negative numbers, so adding half of it to lo is always in range.

The precondition is not checked, and that is the trap

Arrays.binarySearch does not verify that the array is sorted — checking would cost O(n) and destroy the reason you called an O(log n) method. So an unsorted array does not throw. It answers, and the answer is worthless:

int[] unsorted = {5, 1, 9, 3, 7};
for (int t : new int[] {1, 3, 5, 7, 9}) {
    System.out.println("find " + t + " -> " + Arrays.binarySearch(unsorted, t)
        + "   (really at index " + indexOf(unsorted, t) + ")");
}

find 1 -> -1   (really at index 1)
find 3 -> -1   (really at index 3)
find 5 -> 0   (really at index 0)
find 7 -> -3   (really at index 4)
find 9 -> 2   (really at index 2)

It found 5 and 9. It declared 1, 3 and 7 absent when all three are present. Right some of the time is worse than wrong all of the time — wrong all of the time gets noticed in the first test.

Reference

The contract, in full:

Decoding and using the miss, which is the whole reason for the encoding:

List<String> words = new ArrayList<>(List.of("apple", "cherry", "fig"));

int result = Collections.binarySearch(words, "banana");
System.out.println("result          : " + result);

int insertionPoint = -result - 1;
words.add(insertionPoint, "banana");
System.out.println("inserted at " + insertionPoint + "   -> " + words);

result          : -2
inserted at 1   -> [apple, banana, cherry, fig]

That is the idiomatic "insert into a sorted list" — one search, one insert, no re-sort.

Writing it yourself, with the bounds that actually work:

static int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;       // hi is INCLUSIVE, so use <=
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;    // never (lo + hi) / 2
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid - 1;
    }
    return -(lo + 1);                    // lo is the insertion point
}

Pick one convention and keep it. The two that work:

• inclusive hi = length - 1 pairs with while (lo <= hi) and hi = mid - 1;
• exclusive hi = length pairs with while (lo < hi) and hi = mid.

Almost every broken binary search is half of one convention and half of the other — hi = length with lo <= hi reads a[length] and throws.

Scenarios

You need the first match, not any match. The contract says a matching index, so on duplicates you cannot rely on getting the leftmost. Do not try to walk backwards from the result — that is O(n) on an array of equal values, and throws away the reason you used binary search. Change the predicate instead: search for the first element >= target with an exclusive-bound loop that never returns early.

The list is a LinkedList. Collections.binarySearch still works, but each get(mid) walks the chain, so O(log n) comparisons cost O(n) steps each. The JDK special-cases this by iterating instead — it detects RandomAccess — and the result is a search that is no faster than scanning. Binary search assumes indexing is free.

You are searching a range of answers, not an array. Most interview uses of binary search have no array at all: "smallest ship capacity that delivers in D days", "minimum time to finish". The invariant becomes if a workable answer exists, it is in [lo, hi], and a[mid] < target becomes a feasibility test. The loop shape does not change.

The data changes constantly. Binary search needs sorted order, and keeping an array sorted under inserts is O(n) per insert. Past a few thousand mutations a TreeMap or a skip list wins, even though each lookup has a worse constant.

Interviewer's Next Move

1. "Why -(insertion point) - 1 rather than just the negated insertion point?" Because insertion point 0 negates to 0, which is also a legitimate "found at index 0". Every other value would be distinguishable; that one would not. The offset shifts the entire miss range to be strictly negative, so the sign alone tells you which case you are in.

2. "Where is the overflow, and why does hi - lo not have it?" (lo + hi) can exceed Integer.MAX_VALUE when both indices are large, wrapping negative. hi - lo is a difference between two non-negative ints with hi >= lo, so it is between 0 and Integer.MAX_VALUE, and lo plus half of it stays in range. It needs arrays over about a billion elements to bite, which is why it survived in the JDK for nine years.

3. "The array is not sorted. What happens?" Undefined, and specifically not an exception. You get a plausible-looking index or a plausible-looking miss. This is the argument for sorting and searching in the same place in the code, or for holding the data in a structure that cannot be unsorted.

4. "Make it return the first of several equal elements." Stop returning early. Use the exclusive convention, and on a match move hi = mid rather than returning — the loop converges on the leftmost index. The same loop with lo = mid + 1 on a match gives you the upper bound, which is how you count occurrences in O(log n).

5. "How would you binary search a rotated sorted array?" The invariant still holds, but you have to re-establish which half is ordered before you can discard one. Compare a[lo] with a[mid]: exactly one side is sorted, test whether the target lies inside that side's range, and recurse into the other otherwise. Still O(log n), and the usual bug is forgetting that duplicates make "which half is sorted" undecidable, degrading it to O(n).

Check Yourself

Arrays.binarySearch returns -5. What do you know? The value is absent, and it belongs at index 4 — because -(4) - 1 = -5. You also know everything at indices 0 to 3 is smaller than it.

Why must mid be excluded from the next range? It has already been compared and rejected, so keeping it would break the loop's promise that the target is still somewhere in the range. It would also let the range stop shrinking when lo and hi are adjacent, which is an infinite loop rather than a wrong answer.

An interviewer says "it works, I tested it on an array of 10 elements". What do you check? The mid calculation for overflow, and the bound convention — both bugs are invisible at small sizes. Then duplicates, since "any match" may not be the match the caller needs.