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
20returns1(found at index 1) - Searching for
25returns-3- Insertion point = -(-3) - 1 = 3 - 1 = 2
- Element
25should go at index 2, between20and30
- Searching for
5returns-1- Insertion point = -(-1) - 1 = 1 - 1 = 0
- Element
5should 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.