Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 796

Using some algebra and taking a logarithm base-2 of both sides of the equation,
we find that

repetitions log 2 N

We conclude that the binary search algorithm is in the logarithmic complexity
class, or O (log N ).
The runtime of the binary search algorithm doesn't differ much between the best
and worst cases. In the best case, the algorithm finds its target value in the middle on
the first check. In the worst case, the code must perform the full (log N ) comparisons.
But since logarithms are small numbers (log 2 1,000,000 is roughly 20), the perform-
ance is still excellent in the worst case.

Recursive Binary Search
In the previous section, binary search was implemented using an iterative algorithm
with a for loop. But the algorithm can also be implemented elegantly using the con-
cept of recursion introduced in Chapter 12. The recursive version of the method
should accept the same parameters as the standard binary search:

public static int binarySearchR(int[] numbers, int target) {
...

}

But this header will not make it easy to write a recursive solution to the problem.
Recall that the essence of a recursive solution is to break down the problem into
smaller pieces and then solve the sub-problem(s). In this algorithm, the way to shrink
the problem is to examine a smaller and smaller portion of the array until we find the
right index. To do this, we can change our method to accept additional parameters
for the range of indexes (min and max) that currently are being examined. Rather
than changing the header just shown, we can add a private recursive helper with the
additional parameters as described in Chapter 12. The public method can start the
recursive process by calling the helper with 0 and length - 1 as its minimum and
maximum indexes to examine, respectively:

// Recursive binary search algorithm.
// Returns an index at which the target
// appears in the given input array, or -1 if not found.
// pre: array is sorted.
public static int binarySearchR(int[] numbers, int target) {
return binarySearchR(numbers, target, 0, numbers.length - 1);

}

// private recursive helper to implement binary search
private static int binarySearchR(int[] numbers, int target,
int min, int max) {

...

}