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. 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 Sun 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 ones.

Gotchas

Though it is called Collections.binarySearch, the fool thing cannot search arbitrary Collections. It can only search Lists. It should have been called Lists.binarySearch.
The binarySearch method is not part of the Collection interface. It lives in the Collections class. So you cannot say myCollection. binarySearch( key ). You must say Collections. binarySearch( myCollection, key ); However, binarySearch will not work on Collections generally, only Lists.
Collections.binarySearch will not work on arrays. You must use Arrays. binarySearch.

Learning More

Sun’s Javadoc on Arrays.binarySearch : available:

on the web at java.sun.com
in the current JDK 1.6.0_17 or in the old JDK 1.5.0_22 on your local Windows J: drive.

Sun’s Javadoc on Collections.binarySearch : available:

on the web at java.sun.com
in the current JDK 1.6.0_17 or in the old JDK 1.5.0_22 on your local Windows J: drive.

Comparator
hashCode
HashMap
Hashtable
sort

	You can get the freshest copy of this page from:	or possibly from your local J: drive (Java virtual drive/mindprod.com website mirror)
	http://mindprod.com/jgloss/binarysearch.html	J:\mindprod\jgloss\binarysearch.html
	Please email your feedback for publication, errors, omissions, typos, formatting errors, ambiguities, unclear wording, broken/redirected link reports, suggestions to improve this page or comments to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
view Blog	Your face IP:[38.107.191.100]
Feedback	You are visitor number 31,118.