Question:
Recursive Binary Search Java
Use recursive method recursiveBinarySearch to perform a binary search of the array. The method should receive the search key, starting index and ending index as arguments. If the search key is found, returns its index in the array. If the search key is not found, return -1.
// Fig 16.4: BinaryArray.java
// Class that contains an array of random integers and a method
// that uses binary search to find an integer.
import java.util.Random;
import java.util.Arrays;
public class BinaryArray
{
private int[] data; // array of values
private static Random generator = new Random();
// create array of given size and fill with random integers
public BinaryArray( int size )
{
data = new int[ size ]; // create space for array
// fill array with random ints in range 10-99
for ( int i = 0; i < size; i++ )
data[ i ] = 10 + generator.nextInt( 90 );
Arrays.sort( data );
} // end BinaryArray constructor
// perform a binary search on the data
public int binarySearch( int searchElement )
{
int low = 0; // low end of the search area
int high = data.length - 1; // high end of the search area
int middle = ( low + high + 1 ) / 2; // middle element
int location = -1; // return value; -1 if not found
do // loop to search for element
{
// print remaining elements of array
System.out.print( remainingElements( low, high ) );
// output spaces for alignment
for ( int i = 0; i < middle; i++ )
System.out.print( " " );
System.out.println( " * " ); // indicate current middle
// if the element is found at the middle
if ( searchElement == data[ middle ] )
location = middle; // location is the current middle
// middle element is too high
else if ( searchElement < data[ middle ] )
high = middle - 1; // eliminate the higher half
else // middle element is too low
low = middle + 1; // eliminate the lower half
middle = ( low + high + 1 ) / 2; // recalculate the middle
} while ( ( low <= high ) && ( location == -1 ) );
return location; // return location of search key
} // end method binarySearch
// method to output certain values in array
public String remainingElements( int low, int high )
{
StringBuffer temporary = new StringBuffer();
// output spaces for alignment
for ( int i = 0; i < low; i++ )
temporary.append( " " );
// output elements left in array
for ( int i = low; i <= high; i++ )
temporary.append( data[ i ] + " " );
temporary.append( "\n" );
return temporary.toString();
} // end method remainingElements
// method to output values in array
public String toString()
{
return remainingElements( 0, data.length - 1 );
} // end method toString
} // end class BinaryArray
/**************************************************************************
* (C) Copyright 1992-2005 by Deitel & Associates, Inc. and *
* Pearson Education, Inc. All Rights Reserved. *
* *
* DISCLAIMER: The authors and publisher of this book have used their *
* best efforts in preparing the book. These efforts include the *
* development, research, and testing of the theories and programs *
* to determine their effectiveness. The authors and publisher make *
* no warranty of any kind, expressed or implied, with regard to these *
* programs or to the documentation contained in these books. The authors *
* and publisher shall not be liable in any event for incidental or *
* consequential damages in connection with, or arising out of, the *
* furnishing, performance, or use of these programs. *
*************************************************