Collections.binarySearch on Sorted Lists
You'll learn how to use Collections.binarySearch to find elements in sorted lists extremely fast.
What Is Binary Search?
Once you've sorted a list with Collections.sort, you can search it efficiently using Collections.binarySearch. Instead of checking each element one by one (which takes O(n) time), binary search repeatedly cuts the search space in half, achieving O(log n) time complexity.
Think of it like searching for a word in a dictionary. You don't start at page 1 and flip through every page. Instead, you open to the middle, see if your word comes before or after that page, then repeat the process on the relevant half. Each step eliminates half the remaining pages.
How It Works
Binary search requires that your list is already sorted (either naturally or by the same Comparator you pass to binarySearch). The method returns:
- The index of the element if found
- A negative value if not found: specifically
(-(insertion point) - 1), where insertion point is where the element would belong
Basic Usage
List<Integer> numbers = new ArrayList<>(Arrays.asList(2, 5, 8, 12, 16, 23, 38, 56, 72, 91));
// List is already sorted
int index = Collections.binarySearch(numbers, 23);
// Returns 5 (the index where 23 is located)
int notFound = Collections.binarySearch(numbers, 15);
// Returns negative value (around -5 or -6)
// 15 would belong between 12 and 16
With Custom Comparators
If you sorted with a custom Comparator, pass the same Comparator to binarySearch:
Collections.binarySearch(strings, "target", String.CASE_INSENSITIVE_ORDER);
Key Takeaway: Collections.binarySearch finds elements in sorted lists in O(log n) time—drastically faster than sequential search—but the list must be sorted in the same order you're searching.