Assignment #8 CS360

Assignment #8
"Binary Array & Binary Search Test"
09-23-10






/*
Assignment #8
*/

import java.util.Random;
import java.util.Arrays;

public class BinaryArray
{
private int[] data; //array of any value
private static Random generator = new Random();

//create array of any size and fill with random int
public BinaryArray( int size)
{
data = new int[ size ]; //crate space for array

//fill array with int 10-99
for(int i=0; i data [i] = 10 + generator.nextInt( 90 );

Arrays.sort( data );
}

//perform binary search in data
public int binarySearch( int searchElement )
{
int low = 0; //low end of search area
int high = data.length - 1; //high end of search area
int middle = (low + high + 1)/2; //middle element
int location = -1; //return value; -1 if not found

do //loop to search element
{
//print remaining elements of array
System.out.print( remainingElements( low, high ) );

//output spaces for alignment
for(int i=0; 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 high = middle - 1; // eliminate the higher half
else //middle element 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

}

//method to output certain values in array
public String remainingElements( int low, int high )

{

StringBuilder temporary = new StringBuilder();

//output spaces for alignment
for(int i=0; i<=high; i++)
temporary.append("");

//output element left in array
for(int i=low; i<=high; i++)
temporary.append( data[ i ] + "");

temporary.append( "\n");
return temporary.toString();
}

//method to output values in array
public String toString()
{
return remainingElements( 0,data.length - 1);
}
}




~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|




import java.util.Scanner;

public class BinarySearchTest
{
public static void main(String args[] )
{
//create Scanner object to imput data
Scanner input = new Scanner( System.in );

int searchInt; //Search key
int position; //location of search key in array

//create array and output it
BinaryArray searchArray = new BinaryArray( 15 );
System.out.println( searchArray );

//get input from user
System.out.print( "Please enter an integer value (-1 to quit): ");
searchInt = input.nextInt(); //read an int from user
System.out.println();

//repeadtedly ubput an integer; -1 terminates the program
while(searchInt != -1)
{
//use binary search to try to find integer
position = searchArray.binarySearch( searchInt );

//return value of -1 indicates integer was not found
if(position == -1)
System.out.println( "The integer" + searchInt + "was not found.\n");

else
System.out.println( "The integer" + searchInt + "was found in position"
+ position + ".\n" );

//get input from user
System.out.print( "Please enter an integer value (-1 to quit): ");
searchInt = input.nextInt(); //read an int from user
System.out.println();
}
}
}