How does Arrays.binarySearch work, what precondition must hold, and what does it return when the key is absent?
answer
- Precondition: array MUST be sorted (else undefined, no exception)
- O(log n) — halve the range each step
- Miss returns -(insertionPoint) - 1
- Recover insertion point: -(result) - 1
- Search comparator must match sort comparator
basics
~20 sArrays.binarySearch quickly finds a value in a sorted array. The array MUST already be sorted, or results are wrong. If found, it returns the index. If not found, it returns a negative number: -(insertionPoint) - 1.
solid answer
~50 sArrays.binarySearch performs a binary search: it repeatedly halves the search range, so it runs in O(log n) instead of O(n). The critical precondition is that the array is already sorted in ascending order (by natural order, or by the same Comparator you pass to the comparator overload). If it isn't sorted, the result is undefined — you may get a wrong index or a 'not found' even though the element exists, with no exception. On a hit it returns the index of the matching element (and if there are duplicates, no guarantee which one). On a miss it returns a negative value encoded as -(insertionPoint) - 1, where insertionPoint is the index where the key would be inserted to keep the array sorted. That encoding lets you recover the insertion point with -(result) - 1, which is handy for ordered inserts. Always sort first (Arrays.sort) before calling it.
code
java · 14 linesint[] a = {5, 1, 4, 2, 3};
Arrays.sort(a); // {1, 2, 3, 4, 5} — REQUIRED before searching
int hit = Arrays.binarySearch(a, 4); // 3 (index of 4)
int miss = Arrays.binarySearch(a, 6); // -(5)-1 = -6
if (miss < 0) {
int insertionPoint = -(miss) - 1; // 5 -> would go at the end
System.out.println("would insert at " + insertionPoint);
}
// WRONG: searching without sorting first -> result is undefined
int[] unsorted = {5, 1, 4, 2, 3};
int bogus = Arrays.binarySearch(unsorted, 4); // may be wrong, no exceptiongo deeper
Knows binarySearch needs a sorted array and is faster than scanning; can sort then search for a simple int[].
Explains O(log n), the sorted precondition with no exception on violation, and decodes the negative miss return to an insertion point.
Discusses comparator-matching between sort and search, duplicate-index non-determinism, range overloads, and when the sort+search tradeoff beats a HashSet/HashMap lookup.
Reasons about data-structure choice at scale (sorted array + binary search vs. tree/hash structures), cache locality, and designs APIs that keep the sorted invariant safe by construction.
## What 'binary search' means A **binary search** finds an item in a sorted list by repeatedly cutting the search space in half. It checks the middle element: if that equals the key, done; if the key is smaller, search the left half; if larger, the right half. Each step halves the candidates, so it takes about **log₂(n)** comparisons — for a million elements, roughly 20 steps instead of up to a million for a linear scan. This speed is why it's used, and it is the whole reason the method exists separately from a plain loop. ## The non-negotiable precondition: the array must be sorted Binary search's logic depends on order: 'smaller keys are to the left'. If the array is **not sorted ascending**, that assumption is false and the algorithm can walk the wrong way and miss an element that is actually present — or return a meaningless index. Java does **not** check this for you and **does not throw**; the Javadoc explicitly says the result is **undefined** when the array is unsorted. So the rule is: call `Arrays.sort(a)` (or otherwise guarantee order) **before** `Arrays.binarySearch(a, key)`. For object arrays there are two ways order is defined: - `binarySearch(Object[] a, key)` assumes the array is sorted by the elements' **natural order** (their `compareTo`). - `binarySearch(T[] a, key, Comparator<T> c)` assumes the array is sorted by **that same comparator**. The comparator you search with must match the one you sorted with, or results are undefined. ## Return value: found vs. not found - **Found:** returns the index `>= 0` of a matching element. With duplicates, *which* equal element's index you get is **not specified**. - **Not found:** returns a **negative** number computed as `-(insertionPoint) - 1`. The **insertion point** is the index at which the key would have to be inserted to keep the array sorted — i.e. the index of the first element greater than the key, or `a.length` if all elements are smaller. Why the weird formula? A search can never legitimately return a valid index AND signal 'not found', and `0` is a valid index. By making every miss negative and offsetting by one, even an insertion point of `0` becomes `-1` (negative), so the sign cleanly distinguishes hit from miss. To get the insertion point back: `int ip = -(result) - 1;`. This is genuinely useful for maintaining a sorted array: you binary-search, and if missing you know exactly where to splice the new value in. ## Complexity and partial-range search Time is O(log n); space is O(1). There are range overloads `binarySearch(a, fromIndex, toIndex, key)` that search only `[fromIndex, toIndex)`, useful when the array has a sorted prefix. ## Common pitfalls 1. Searching an **unsorted** array — silent wrong answers. 2. Forgetting a miss is **negative** and treating the return directly as an index (a `-1`..`-(n+1)` value indexes nothing valid). 3. **Mismatched comparator** between sort and search. 4. Assuming a specific index among **duplicates**. ## Mental model Binary search is a fast lookup that trades a one-time sorting cost for log-time queries. The negative-return trick is its way of telling you 'not here, but here's exactly where it would go'.
- If the key isn't found and binarySearch returns -6, where would you insert it?Insertion point = -(-6) - 1 = 5. The key belongs at index 5 to keep the array sorted (here, the end).
- What happens if you sort with one Comparator but binary-search with a different one?The result is undefined. binarySearch assumes the array is ordered by the comparator (or natural order) you pass; a mismatch breaks the 'smaller is left' invariant, so it can miss present elements.
saying these in an interview costs you the question
- Calling binarySearch on an unsorted array and trusting the result
- Treating the negative miss return as a valid index
- Assuming a particular index is returned for duplicate elements
- Expecting an exception when the array isn't sorted