Java Reference
In-Depth Information
3. For each of the cases that involve recursion, if all recursive calls perform their
actions correctly, then the entire case performs correctly: There are two cases in
which there are recursive calls, when key < a[mid] and when key > a[mid] . We need
to check each of these two cases.
First suppose key < a[mid] . In this case, since the array is sorted, we know that if
key is anywhere in the array, then key is one of the elements a[first] through
a[mid 1] . Thus, the method need only search these elements, which is exactly
what the recursive call
search(a, first, mid 1, key)
does. So if the recursive call is correct, then the entire action is correct.
Next, suppose key > a[mid] . In this case, since the array is sorted, we know that if
key is anywhere in the array, then key is one of the elements a[mid + 1] through
a[last] . Thus, the method need only search these elements, which is exactly what
the recursive call
search(a, mid + 1, last, key)
does. So if the recursive call is correct, then the entire action is correct. Thus, in
both cases the method performs the correct action (assuming that the recursive calls
perform the correct action).
The method search passes all three of our tests, so it is a good recursive method definition.
Efficiency of Binary Search
The binary search algorithm is extremely fast compared to an algorithm that simply
tries all array elements in order. In the binary search, you eliminate about half the
array from consideration right at the start. You then eliminate a quarter, then an
eighth of the array, and so forth. These savings add up to a dramatically fast algorithm.
For an array of 100 elements, the binary search will never need to compare more than
seven array elements to the key. A serial search could compare as many as 100 array
elements to the key and on the average will compare about 50 array elements to the
key. Moreover, the larger the array is, the more dramatic the savings will be. On an
array with 1,000 elements, the binary search will only need to compare about 10 array
elements to the key value, as compared to an average of 500 for the serial search algo-
rithm. 1
An iterative version of the method search is given in Display 11.9. On some systems
the iterative version will run more efficiently than the recursive version. The algorithm
for the iterative version was derived by mirroring the recursive version. In the iterative
version, the local variables first and last mirror the roles of the parameters in the
recursive version, which are also named first and last . As this example illustrates, it
iterative
version
1 The binary search algorithm has worst-case running time that is logarithmic, that is O (log n ). The
serial search algorithm is linear, that is O ( n ). If the terms used in this footnote are not familiar to you,
you can safely ignore this footnote.
Search WWH ::




Custom Search