Java Glossary : binary search

Java definitions: 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

You are here : home : Java Glossary : B words : binary search.

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.

home	Canadian Mind Products
	mindprod.com IP:[24.87.56.253]
	Your IP:[80.134.30.163]
	You are visitor number 3123.
	Please send errors, omissions and suggestions
	to improve this page to Roedy Green.
	You can get a fresh copy of this page from:	or possibly from your local J: drive mirror:
	http://mindprod.com/jgloss/binarysearch.html	J:\mindprod\jgloss\binarysearch.html