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.

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

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.7.0_17 or in the old JDK 1.6.0_45 on your local Windows J: drive.

Oracle’s Javadoc on Collections.binarySearch : available:

on the web at Oracle.com
in the current JDK 1.7.0_17 or in the old JDK 1.6.0_45 on your local Windows J: drive.

Comparator
hashCode
HashMap
Hashtable
sort

	available 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 email your feedback for publication, letters to the editor, errors, omissions, typos, formatting errors, ambiguities, unclear wording, broken/redirected link reports, suggestions to improve this page or comments to Roedy Green : . If you want your message, your name or email kept confidential, not considered for public posting, please explicitly specify that. Unless you state otherwise, I will treat your message as a letter to the editor that I may or may not publish in the feedback section. After that, it will be too late to retract it. If you disagree with something I said, especially when sending an ad-hominem attack, a rant composed mainly of obscenities or a death threat, please quote the offending passage and cite the web page where you found it, tell me why you think it is wrong, and, if possible, provide some supporting evidence. I can’t very well fix erroneous or ambiguous text if I can’t find it.
Blog	Canadian Mind Products IP:[65.110.21.43] Your face IP:[54.242.233.11]
Feedback	You are visitor number 46,968.