Algorithms in a Nutshell

Binary Search | 113

Searching

Input/Output

The input to BINARYSEARCHis an indexed collectionAof elements. Each

elementA[i] has akeyvaluekithat can be used to identify the element. These keys

are totally ordered, which means that given two keys,kiandkj, eitherki<kj,ki=kj,

orki>kj. We construct a data structure that holds the elements (or pointers to the

elements) and preserves the ordering of the keys. We must also be able to divide

the data structure into subsets as we search, so that we solve the search problem

in a “divide and conquer” manner. The output to BINARYSEARCHis eithertrue

orfalse.

Context

Whether searching through a set of numbers or a list of names ordered alphabeti-

cally, the method works. It can be shown that a logarithmic number of probes is

necessary in the worst case.

Forces

The keys for the elements in the collection must admit a total ordering that lets

you test whether an element is “greater than or equal” to another. Different types

of data structures support binary searching. If the collection is static, the elements

can be placed into an array. This makes it easy to navigate through the collection.

However, if you need to add or remove elements from the collection, this

approach becomes unwieldy. There are several structures one can use; one of the

best known is the binary tree, discussed later in “Variations.”

Solution

Given an ordered collection of elements as an array, the Java code in Example 5-5

shows a parameterized implementation of BINARYSEARCHfor any base typeT

(using the capability of Java generics). Java provides thejava.util.Comparable

interface that contains a single method,compareTo. Any class that correctly imple-

ments this interface guarantees a total ordering of its instances.

Example 5-5. Binary Search implementation in Java

package algs.model.search;

/**

* Binary Search given a pre-sorted array of the parameterized type.

*

* @param T elements of the collection being searched are of this type.

* The parameter T must implement Comparable.

*/

public class BinarySearch<T extends Comparable<T>> {

/* Search for target in collection. Return true on success. */

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use