Algorithms in a Nutshell

(^114) | Chapter 5: Searching
Three variables are used in the implementation:low,high, andix.lowis the
lowest index of the current subarray being searched,highis the upper index of the
same subarray, andixis the midpoint of the subarray. The performance of this
code depends on the number of times the loop executes.
Consequences
BINARYSEARCHadds a small amount of complexity for large performance gains.
The complexity can increase when the collection is not stored in a simple in-
memory data structure, such as an array. There must be a way to access element
A[i] for 0≤i<nin the collection based upon the natural order of the elements in the
collection, as represented by theComparableinterface. A large collection might
need to be kept in secondary storage, such as a file on a disk. In such a case, the
ithelement is accessed by its offset location within the file. Using secondary
storage, the time required to search for an element is dominated by the costs to
accessing the storage; other solutions related to BINARYSEARCHmay be appro-
priate. See “Variations” for algorithms that address these issues.
Analysis
BINARYSEARCHdivides the problem size approximately in half every time it
executes the loop. The maximum number of times the collection of sizenis cut in
half is log (n), ifnis a power of 2; otherwise, it is⎣log (n)⎦. If we use a single oper-
ation to determine whether two items are equal, lesser than, or greater than (as is
made possible by theComparableinterface), then only⎣log (n)⎦comparisons are
needed, resulting in a classification of O(logn).
public boolean search(T[] collection, T target) {
// null is never included in the collection
if (target == null) { return false; }
int low = 0, high = collection.length - 1;
while (low <= high) {
int ix = (low + high)/2;
int rc = target.compareTo(collection[ix]);
if (rc < 0) {
// target is less than collection[i]
high = ix - 1;
} else if (rc > 0) {
// target is greater than collection[i]
low = ix + 1;
} else {
// found the item.
return true;
}
}
return false;
}
}
Example 5-5. Binary Search implementation in Java (continued)
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
Licensed by
Ming Yi