Java Reference
In-Depth Information
The linear search algorithm runs in
O
(
n
) time. The worst case in this algorithm is that ev-
ery element must be checked to determine whether the search item exists in the array. If
the size of the array is
doubled
, the number of comparisons that the algorithm must per-
form is also
doubled
. Linear search can provide outstanding performance if the element
matching the search key happens to be at or near the front of the array. But we seek algo-
rithms that perform well, on average, across
all
searches, including those where the ele-
ment matching the search key is near the end of the array.
Linear search is easy to program, but it can be slow compared to other search algo-
rithms. If a program needs to perform many searches on large arrays, it's better to imple-
ment a more efficient algorithm, such as the binary search, which we present next.
Performance Tip 19.1
Sometimes the simplest algorithms perform poorly. Their virtue is that they're easy to pro-
gram, test and debug. Sometimes more complex algorithms are required to realize maxi-
mum performance.
The
binary search algorithm
is more efficient than linear search, but it requires that the
array be sorted. The first iteration of this algorithm tests the
middle
element in the array.
If this matches the search key, the algorithm ends. Assuming the array is sorted in
ascend-
ing
order, then if the search key is
less than
the middle element, it cannot match any ele-
ment in the second half of the array and the algorithm continues with only the first half
of the array (i.e., the first element up to, but not including, the middle element). If the
search key is
greater than
the middle element, it cannot match any element in the first half
of the array and the algorithm continues with only the second half (i.e., the element
after
the middle element through the last element). Each iteration tests the middle value of the
remaining portion of the array. If the search key does not match the element, the algo-
rithm eliminates half of the remaining elements. The algorithm ends by either finding an
element that matches the search key or reducing the subarray to zero size.
Example
As an example consider the sorted 15-element array
2 3 5 10 27 30 34 51 56 65 77 81 82 93 99
and a search key of 65. A program implementing the binary search algorithm would first
check whether 51 is the search key (because 51 is the
middle
element of the array). The
search key (65) is larger than 51, so 51 is ignored along with the first half of the array (all
elements smaller than 51), leaving
56 65 77 81 82 93 99
Next, the algorithm checks whether 81 (the middle element of the remainder of the
array) matches the search key. The search key (65) is smaller than 81, so 81 is discarded
along with the elements larger than 81. After just two tests, the algorithm has narrowed
the number of values to check to only three (56, 65 and 77). It then checks 65 (which
indeed matches the search key) and returns the index of the array element containing 65.
