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

Collections.binarySearch on Sorted Lists

Learn how binarySearch efficiently finds elements in sorted lists in O(log n) time.

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.