Recursion - Data Structures and Problem Solving Using Java - page 308

1 /**
2 * Performs the standard binary search using two comparisons
3 * per level. This is a driver that calls the recursive method.
4 * @return index where item is found or NOT_FOUND if not found.
5 */
6 public static <AnyType extends Comparable<? super AnyType>>
7 int binarySearch( AnyType [ ] a, AnyType x )
8 {
9 return binarySearch( a, x, 0, a.length -1 );
10 }
11
12 /**
13 * Hidden recursive routine.
14 */
15 private static <AnyType extends Comparable<? super AnyType>>
16 int binarySearch( AnyType [ ] a, AnyType x, int low, int high )
17 {
18 if( low > high )
19 return NOT_FOUND;
20
21 int mid = ( low + high ) / 2;
22
23 if( a[ mid ].compareTo( x ) < 0 )
24 return binarySearch( a, x, mid + 1, high );
25 else if( a[ mid ].compareTo( x ) > 0 )
26 return binarySearch( a, x, low, mid - 1 );
27 else
28 return mid;
29

figure 7.11
A binary search
routine, using
recursion

}

recursive call on the appropriate subarray (line 24 or 26) if a match has not
been detected. When a match is detected, the matching index is returned at
line 28.
Note that the running time, in terms of Big-Oh, is unchanged from the
nonrecursive implementation because we are performing the same work. In
practice, the running time would be expected to be slightly larger because of
the hidden costs of recursion.

drawing a ruler
Figure 7.12 shows the result of running a Java program that draws ruler mark-
ings. Here, we consider the problem of marking 1 inch. In the middle is the
longest mark. In Figure 7.12, to the left of the middle is a miniaturized ver-
sion of the ruler and to the right of the middle is a second miniaturized ver-
sion. This result suggests a recursive algorithm that first draws the middle line
and then draws the left and right halves.