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

binarySearch Return Values and Insertion Points

Understand binarySearch's negative return values indicating where an element would be inserted.

binarySearch Return Values and Insertion Points

You'll learn how to interpret the negative return values from Collections.binarySearch to find where missing elements should be inserted.

Understanding Positive Return Values

When Collections.binarySearch finds the element you're searching for, it returns the index where that element exists in the list. Simple enough! But what happens when the element isn't found?

Negative Return Values: The Insertion Point Formula

When binarySearch doesn't find the element, it returns a negative number that encodes useful information: where the element would belong if you were to insert it while maintaining sorted order.

The formula is: -(insertion point) - 1

To get the actual insertion point from a negative return value, reverse the formula:

insertion point = -(return value) - 1

Or equivalently: insertion point = -(return value + 1)

Why the Encoding?

This encoding ensures negative returns never conflict with valid indices. Index 0 would become -1, index 1 would become -2, and so on. This way, you can always distinguish "found" from "not found" with a simple sign check.

Practical Example

Imagine a sorted list: [10, 20, 30, 50]

  • Searching for 20 returns 1 (found at index 1)
  • Searching for 25 returns -3
    • Insertion point = -(-3) - 1 = 3 - 1 = 2
    • Element 25 should go at index 2, between 20 and 30
  • Searching for 5 returns -1
    • Insertion point = -(-1) - 1 = 1 - 1 = 0
    • Element 5 should go at the beginning

Think of it like this: the return value is a treasure map. Positive values say "here it is!" while negative values say "here's where it should be!"

Key Takeaway: Collections.binarySearch returns negative values for missing elements, encoded as -(insertion point) - 1, allowing you to determine exactly where to insert the element to maintain sorted order.