binary search : Java Glossary

*0-9ABCDEFGHIJKLMNOPQRSTUVWXYZ (all)

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.

Insertion Point

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 either:
insertionPoint = -( r + 1 );
// or
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.

Poor Performance

Binary search is slow. You are better off to use linear search for small searches and HashSet for big

Gotchas

Learning More

Oracle’s Javadoc on Arrays.binarySearch : available:
Oracle’s Javadoc on Collections.binarySearch : available:

This page is posted
on the web at:

http://mindprod.com/jgloss/binarysearch.html

Optional Replicator mirror
of mindprod.com
on local hard disk J:

J:\mindprod\jgloss\binarysearch.html
Canadian Mind Products
Please the feedback from other visitors, or your own feedback about the site.
Contact Roedy. Please feel free to link to this page without explicit permission.

IP:[65.110.21.43]
Your face IP:[54.85.255.74]
You are visitor number