binary search : Java Glossary

* 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 (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

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

Oracle’s Javadoc on Arrays.binarySearch : available:

on the web at Oracle.com
in the current JDK 1.8.0_131 on your local Windows J: drive.

Oracle’s Javadoc on Collections.binarySearch : available:

on the web at Oracle.com
in the current JDK 1.8.0_131 on your local Windows J: drive.

Comparator
hashCode
HashMap
Hashtable
sort

standard footer
	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
	Please read the feedback from other visitors, or send your own feedback about the site. Contact Roedy. Please feel free to link to this page without explicit permission.
	Canadian Mind Products IP:[65.110.21.43] Your face IP:[3.16.68.10]
Feedback	You are visitor number