Java Reference
In-Depth Information
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.
6.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 ascend-
ing 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 6.10 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.
You now know how the binary search works. The next task is to implement it in Java.
Don't rush to give a complete implementation. Implement it incrementally, one step at a time.
You may start with the first iteration of the search, as shown in Figure 6.11a. It compares the
key with the middle element in the list whose
low
index is
0
and
high
index is
list.length - 1
. If
key < list[mid]
, set the
high
index to
mid - 1
; if
key ==
list[mid]
, a match is found and return
mid
; if
key > list[mid]
, set the
low
index to
mid + 1
.
Next consider implementing the method to perform the search repeatedly by adding a loop,
as shown in Figure 6.11b. The search ends if the key is found, or if the key is not found when
low > high
.
When the key is not found,
low
is the insertion point where a key would be inserted to
maintain the order of the list. It is more useful to return the insertion point than
-1
. The
method must return a negative value to indicate that the key is not in the list. Can it simply
return
-low
? No. If the key is less than
list[0]
,
low
would be
0
.
-0
is
0
. This would
binary search animation on
Companion Website
why not -1?
