binary search : Java Glossary
- binary search
A technique for finding an element in a sorted list by dividing the list in two and
deciding which half the sought after element lives in, then dividing the list in two
again, gradually narrowing down the possible location of the sought after element.
Its advantage is that it takes no extra RAM (Random Access Memory).
It is faster than ArrayList.contains which simply
compares every element in the collection. Binary search requires log₂ n
compares vs n/2 compares for a linear search. You invoke it with:
binarySearch tells you where it found the match, and if
it does not find a match, it tells you where the match would have been. binarySearch also has a variant that takes a Comparator to define a custom ordering. The elements must be in
order by that Comparator. Collections.binarySearch works on List
collections. Though binarySearch works on any
List, it really should only be use on Lists that
implement RandomAccess such as Vector or ArrayList. Without RandomAccess, binarySearch degenerates
to a linear search.
Binary search with a Comparator
If your List is not in natural order, you can
still use binarySearch, but you need a Comparator to describe the order. It is up to you to keep the list
in sorted order. binarySearch does not sort it for you.
binarySearch returns a number. If
it is positive, it is the slot where the match was found. If it is negative, there
was no match, and it returns a value that indicates where the key would fit in if you
were to insert it. However, binarySearch does not return
the insertion point directly. If the result in negative, you must do a calculation
insertionPoint = -( r + 1 );
insertionPoint = -r - 1;
Why did Oracle screw around this way? Why didn’t they just return the insertion
point directly? The problem is, what if the insertion point were 0? You could not
tell that apart from a match found in slot 0. The way it works, an insert at 0 is
coded as -1.
Binary search is slow. You are better off to
use linear search for small searches and HashSet for big
Oracle’s Javadoc on Arrays.binarySearch
Oracle’s Javadoc on Collections.binarySearch