Course contentsShow
← Java
Lesson 1224 of 2,87028. Collections Utility ClassFree lesson

Preconditions for binarySearch Correctness

Recognize that binarySearch requires the list to be sorted, or results are undefined.

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.