Preconditions for binarySearch Correctness
You'll learn: Why Collections.binarySearch() requires your list to be sorted beforehand, or else your results become unpredictable.
Why Sorting Matters
Binary search works by repeatedly dividing the search space in half. It examines the middle element and decides whether the target must be in the left half or the right half—but this logic only works if the data is sorted.
Think of looking up a word in a dictionary. You open to the middle, see "M," and know that "zebra" must be in the second half. But if the dictionary pages were shuffled randomly, this strategy would fail completely. You might skip right past "zebra" based on a false assumption.
The Critical Rule
You must sort the list before calling binarySearch(). If the list isn't sorted according to the natural ordering (or the Comparator you're using), the method may:
- Return an incorrect index
- Return a "not found" result even when the element exists
- Return a random, meaningless position
The Java documentation explicitly states that results are undefined for unsorted lists. "Undefined" means the method won't throw an error—it'll silently give you wrong answers.
Matching Sort and Search Criteria
If you sorted with a custom Comparator, you must pass that same Comparator to binarySearch(). The search algorithm needs to make the same "left or right?" decisions that the sort made.
Key Takeaway: Collections.binarySearch() is only guaranteed to work correctly on sorted lists. Always call Collections.sort() first (using matching criteria), or your search results will be unreliable. Sorting and searching must use the same ordering rules.