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

Our recursive binary search method accepts the minimum and maximum indexes
of interest as parameters. On each pass of the recursive algorithm, the code examines
the middle element. If this element is too small, the code recursively examines only
the right half of the array. If the middle element is too large, the code recursively
examines only the left half. This process repeats, recursively calling itself with differ-
ent values of min and max , until it finds the target or until the entire array has been
eliminated from consideration. The following code implements the algorithm:
// 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.
private static int binarySearchR(int[] numbers, int target,
int min, int max) {
// base case
if (min > max) {
return -1; // not found
} else {
// recursive case
int mid = (max + min) / 2;
if (numbers[mid] == target) {
return mid;
} else if (numbers[mid] < target) {
return binarySearchR(numbers, target, mid + 1, max);
} else {
return binarySearchR(numbers, target, min, mid - 1);
}
}
}
Some instructors don't like recursive versions of methods like binary search
because there is a nonrecursive solution that's fairly easy to write and because recur-
sion tends to have poor runtime performance because of the extra method calls it
generates. However, that doesn't pose a problem here. The runtime of the recursive
version of our binary search method is still O (log N ), because it's essentially per-
forming the same computation; it's still cutting the input in half at each step. In fact,
the recursive version is fast enough that the computer still can't time it accurately. It
produces a runtime of 0 ms even on arrays of tens of millions of integers.
In general, analyzing the runtimes of recursive algorithms is tricky. Recursive run-
time analysis often requires a technique called recurrence relations , which are mathe-
matical relations that describe an algorithm's runtime in terms of itself. That's a com-
plex topic for a later course that won't be covered in this textbook.