Java Reference
In-Depth Information
of the element in the array that matches the key. If no match is found, the search returns
-1
.
The
linearSearch
method in Listing 7.6 gives the solution.
linear search animation on
Companion Website
L
ISTING
7.6
LinearSearch.java
1
public class
LinearSearch {
2
/** The method for finding a key in the list */
3
public static int
linearSearch(
int
[] list,
int
key) {
4
for
(
int
i =
0
; i < list.length; i++) {
5
if
(key == list[i])
6
return
i;
[0] [1] [2] …
7 }
8
return
-
1
;
9}
10 }
list
key Compare key with
list[i]
for
i
= 0, 1, …
To better understand this method, trace it with the following statements:
1
int
[] list = {
1
,
4
,
4
,
2
,
5
,
-3
,
6
,
2
};
2
int
i = linearSearch(list,
4
);
// Returns 1
3
int
j = linearSearch(list,
-4
);
// Returns -1
4
int
k = linearSearch(list,
-3
);
// Returns 5
The linear search method compares the key with each element in the array. The elements can
be in any order. On average, the algorithm will have to examine half of the elements in an
array before finding the key, if it exists. Since the execution time of a linear search increases
linearly as the number of array elements increases, linear search is inefficient for a large array.
7.10.2 The Binary Search Approach
Binary search is the other common search approach for a list of values. For binary search to
work, the elements in the array must already be ordered. Assume that the array is in ascending
order. The binary search first compares the key with the element in the middle of the array.
Consider the following three cases:
If the key is less than the middle element, you need to continue to search for the key
only in the first half of the array.
■
If the key is equal to the middle element, the search ends with a match.
■
If the key is greater than the middle element, you need to continue to search for the
key only in the second half of the array.
■
Clearly, the binary search method eliminates at least half of the array after each comparison.
Sometimes you eliminate half of the elements, and sometimes you eliminate half plus one.
Suppose that the array has
n
elements. For convenience, let
n
be a power of
2
. After the first
comparison,
n/2
elements are left for further search; after the second comparison,
(n/2)/2
elements are left. After the
k
th comparison,
n/2
k
elements are left for further search. When
k = log
2
n
, only one element is left in the array, and you need only one more comparison.
Therefore, in the worst case when using the binary search approach, you need
log
2
n+1
com-
parisons to find an element in the sorted array. In the worst case for a list of
1024
(2
10
) ele-
ments, binary search requires only
11
comparisons, whereas a linear search requires
1023
comparisons in the worst case.
The portion of the array being searched shrinks by half after each comparison. Let
low
and
high
denote, respectively, the first index and last index of the array that is currently being
searched. Initially,
low
is
0
and
high
is
list.length-1
. Let
mid
denote the index of the
middle element, so
mid
is
(low + high)/2
. Figure 7.9 shows how to find key
11
in the list
{
2
,
4
,
7
,
10
,
11
,
45
,
50
,
59
,
60
,
66
,
69
,
70
,
79
} using binary search.
binary search animation on
Companion Website
Search WWH ::
Custom Search