Page 821 - Introduction to Programming with Java: A Problem Solving Approach

look at each item, individually. If the array is very short, a sequential search is also the fastest way to search,
Apago PDF Enhancer
because a sequential search is very simple. If the array is long, however, and if it’s relatively stable, it’s often faster to sort the array and then use a binary search. (Chapter 10 describes sorting algorithms.)
Why is a binary search faster than a sequential search? The number of steps required for a sequen- tial search equals <array>.length, but the number of steps required in a binary search equals only log2(<array>.length). For example, if there are one million items in the array, that’s one million steps for a sequential search but only about 20 steps for a binary search. Even if a typical binary-search step is more complicated than a typical sequential-search step, the binary search will still be significantly faster when the array is very long.
It’s appropriate to use recursion to implement a binary search. The way to make the problem simpler is to divide the array into two nearly equally sized arrays, and continue dividing until each half contains no more than one element, which is the stopping condition. Figure A8.4 shows our implementation of this al- gorithm. We have included shaded print statements at appropriate places in the code to show what the code is doing when it executes. After debugging the program, you would want to remove all of these shaded print statements.
Figure A8.5 shows a driver that demonstrates the binary search algorithm implemented in Figure A8.4. In the output section, the shaded areas are outputs generated by the shaded print statements in Figure A8.4. In this recursion the real work is done while the process is drilling down to the stopping condition. Notice how the first and last values converge on the match or the place where the match would be if it were there. The answer is generated at the point when the stopping condition is reached. The nested returns just pass this answer back. When you remove the shaded print statements from Figure A8.4, the only output you will see is the un-shaded parts of the output.
Appendix 8 Recursion 787
private static int factorial(int n)
{
}
// end factorial
if (n == 0) // stopping condition
{
}
else
{
}
return 1;
return n * factorial(n-1);
Figure A8.3 Cleaner implementation of factorial method Binary Search of an Ordered Array
Now let’s look at another example that is a little harder to implement with loops and makes a better case for recursion. In this case, you’ll see that all the useful work is done while the algorithm is drilling down to the stopping condition and the returns just pass the answer back.
Here’s the problem: Suppose you want to find the location of a particular value in an array. This is a
common database operation. If the array is not sorted, the best you can do is use a sequential search and