Java Reference
In-Depth Information
Lines 10-39 declare method
binarySearch
, which receives as parameters the array to
search (
data
) and the search key (
key
). Lines 12-14 calculate the
low
end index,
high
end
index and
middle
index of the portion of the array that the program is currently searching.
At the beginning of the method, the
low
end is
0
, the
high
end is the length of the array
minus
1
and the
middle
is the average of these two values. Line 15 initializes the
location
of the element to
-1
—the value that will be returned if the
key
is not found. Lines 17-36
loop until
low
is greater than
high
(this occurs when the
key
is not found) or
location
does not equal
-1
(indicating that the
key
was found). Line 28 tests whether the value in
the
middle
element is equal to the
key
. If so, line 29 assigns
middle
to
location
, the loop
terminates and
location
is returned to the caller. Each iteration of the loop tests a single
value (line 28) and
eliminates half of the remaining values in the array
(line 31 or 33) if the
value is not the
key
.
In the worst-case scenario, searching a
sorted
array of 1023 elements takes
only 10 compar-
isons
when using a binary search. Repeatedly dividing 1023 by 2 (because after each com-
parison we can eliminate half the array) and rounding down (because we also remove the
middle element) yields the values 511, 255, 127, 63, 31, 15, 7, 3, 1 and 0. The number
1023 (2
10
- 1) is divided by 2 only 10 times to get the value 0, which indicates that there
are no more elements to test. Dividing by 2 is equivalent to one comparison in the binary
search algorithm. Thus, an array of 1,048,575 (2
20
- 1) elements takes a
maximum of 20
comparisons
to find the key, and an array of over one billion elements takes a
maximum of
30 comparisons
to find the key. This is a tremendous improvement in performance over
the linear search. For a one-billion-element array, this is a difference between an average
of 500 million comparisons for the linear search and a maximum of only 30 comparisons
for the binary search! The maximum number of comparisons needed for the binary search
of any sorted array is the exponent of the first power of 2 greater than the number of
elements in the array, which is represented as log
2
n
. All logarithms grow at roughly the
same rate, so in big O notation the base can be omitted. This results in a big O of
O
(
log
n
)
for a binary search, which is also known as
logarithmic run time
and pronounced as
“order log n.”
Sorting data (i.e., placing the data into some particular order, such as ascending or de-
scending) is one of the most important computing applications. A bank sorts all checks by
account number so that it can prepare individual bank statements at the end of each
month. Telephone companies sort their lists of accounts by last name and, further, by first
name to make it easy to find phone numbers. Virtually every organization must sort some
data, and often massive amounts of it. Sorting data is an intriguing, computer-intensive
problem that has attracted intense research efforts.
An important item to understand about sorting is that the end result—the sorted
array—will be the
same
no matter which algorithm you use to sort the array. The choice
of algorithm affects only the run time and memory use of the program. The rest of this
chapter introduces three common sorting algorithms. The first two—
selection sort
and
insertion sort
—are easy to program but
inefficient
. The last algorithm—
merge sort
—is
