Recursion - Absolute Java - page 674

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, because 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, because 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 7 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 algorithm. 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

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 it.