Binary Search Preconditions

Binary search requires the searched range to be sorted according to the same ordering used by the search. If that precondition is violated, the result is not reliable and may fail to find an existing value.

Binary search repeatedly compares the target with the middle element and discards half of the remaining range. This elimination step is valid only when the elements have a consistent ordering, so the algorithm can determine which half cannot contain the target.

For Java arrays, `Arrays.binarySearch` expects the relevant range to be sorted in ascending natural order when using the overload without a comparator. For comparator-based overloads, the range must instead be sorted according to that comparator.

The same idea applies to `Collections.binarySearch` for lists. The list must be sorted according to the ordering used for the search; otherwise, the returned index has no dependable meaning.

The precondition applies to the range being searched, not necessarily to unrelated elements outside that range. When using an overload that specifies `fromIndex` and `toIndex`, only that selected range needs to satisfy the ordering requirement.

Key points

• The searched range must be sorted before binary search.
• The sort order must match the search order.
• Natural-order searches require natural-order sorting.
• Comparator-based searches require sorting with the same comparator.
• An unsorted range can produce an incorrect result even when the target exists.

Interview questions

Why must an array be sorted before binary search?

Binary search decides which half of the range can be discarded after comparing the target with the middle element. That decision depends on the elements being ordered consistently. Without sorting, a larger or smaller value can appear on either side of the midpoint, so discarding a half is not justified. The algorithm may therefore miss an existing target.

What ordering should be used with `Arrays.binarySearch`?

For the overload that does not take a comparator, the array should be sorted according to its natural ordering. If a comparator overload is used, the array should be sorted according to that comparator. The sorting and searching rules must therefore agree. Otherwise, the binary-search decisions are not guaranteed to be valid.

What happens if you call binary search on an unsorted array?

The result is not generally meaningful because the algorithm's correctness depends on the sorted-order precondition. It might return an index that does not contain the target, or indicate that the target is absent even when it exists. The exact behavior depends on the data and search implementation. You should not use a binary-search result as proof of membership when the ordering precondition was violated.

Does binary search require the entire array or list to be sorted?

Not necessarily. If an API overload searches a specified subrange, the relevant subrange must satisfy the ordering requirement. Elements outside that range do not participate in that particular search. For example, an array can contain an unsorted suffix while a separately specified prefix remains properly ordered for the search.