Collection Search in Java
Problem
Collections.binarySearch() locates an element in logarithmic time, but only works correctly on a list that's already sorted — the same requirement a manual binary search would have.
Given an unsorted list of numbers, sort it and then find the index of a specific value using Collections.binarySearch().
Java Program
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class CollectionSearchDemo {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
numbers.add(42);
numbers.add(7);
numbers.add(19);
numbers.add(3);
numbers.add(56);
Collections.sort(numbers); // binarySearch() requires a sorted list
int index = Collections.binarySearch(numbers, 19);
System.out.println("Found 19 at index: " + index);
}
}Output
Core Logic
Sorting the list first satisfies binarySearch()'s precondition, and once that's done, a single call locates the target far faster than scanning every element.
- 1
Collections.sort(numbers)puts the list into ascending order —[3, 7, 19, 42, 56]— a required first step. - 2
Collections.binarySearch(numbers, 19)repeatedly halves the search range, comparing the midpoint against19each time. - 3Because the list is sorted, each comparison rules out half of the remaining candidates, honing in on the target quickly.
- 4The method returns the target's index directly —
2here — once it's found.
[3, 7, 19, 42, 56], binary search lands on 19 at index 2 in just two comparisons.Key Point: Calling binarySearch() on a list that isn't actually sorted doesn't throw an error — it just silently returns an unreliable result, since the algorithm assumes sortedness rather than checking for it.
Why: Sorting the list first costs O(n log n) and dominates the overall cost here; binarySearch() itself only takes O(log n) once the list is sorted, and TimSort's merge step needs a temporary array proportional to n.