binary search : Java Glossary

2008-02-15 by Roedy Green ©1996-2008 Canadian Mind Products
Go to : punctuation 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z (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. 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:

boolean found = Arrays.binarySearch ( stringArray, stringToSearchFor ) >= 0;

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.

Learning More

Sun’s Javadoc on Arrays.binarySearch : available:

on the web at java.Sun.com
in the JDK 1.6.0_06 or in JDK 1.5.0_15 on your local J: drive.

Sun’s Javadoc on Collections.binarySearch : available:

on the web at java.Sun.com
in the JDK 1.6.0_06 or in JDK 1.5.0_15 on your local J: drive.

Comparator
hashCode
HashMap
Hashtable

	Please email your feedback for publication, errors, omissions, broken/redirected link reports and suggestions to improve this page to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
	Your face IP:[38.103.63.16]	The information on this page is for non-military use only.
	You are visitor number 21,924.	Military use includes use by defence contractors.
	You can get a fresh copy of this page from:	or possibly from your local J: drive (Java virtual drive/Mindprod website mirror)
	http://mindprod.com/jgloss/binarysearch.html	J:\mindprod\jgloss\binarysearch.html