// Arup Guha
// 1/19/09
// Solution to AP CS Assignment: Binary Search 

import java.util.*;

public class BinSearch {
	
	final static int NOT_FOUND = -1;

	public static void main(String[] args) {
		
		Scanner stdin = new Scanner(System.in);
		Random r = new Random();
		
		System.out.println("Here is a list of the numbers");
		
		// Make, sort and print out the array.
		int[] values = makeRandArray(r, 10, 100);
		Arrays.sort(values);
		printArray(values);
		
		String answer;
		
		// Get the user's first answer.
		System.out.println("Would you like to search for a number?");
		answer = stdin.next();
		
		// Keep on going so long as they want to search.
		while (answer.equalsIgnoreCase("yes")) {
			
			// Find the value for which to search.
			System.out.println("What number would you like to search for?");
			int search = stdin.nextInt();
			
			// Search for it.
			int retVal = binarySearch(values, search);
			
			// Found it.
			if (retVal > -1) 
				System.out.println(search+" was found in the array, in index "+ retVal+".");
				
			// Not in the array.
			else
				System.out.println(search+" was NOT found in the array.");
				
			// Give the user another chance to search.
			System.out.println("Would you like to search for a number?");
			answer = stdin.next();
		}
	}	
	
	// Returns an array with size elements which are each random integers
	// from 0 to max-1.
	public static int[] makeRandArray(Random r, int size, int max) {
		
		// Allocate space for the array.
		int[] array = new int[size];
		
		// Fill in each value.
		for (int i=0; i<size; i++)
			array[i] = r.nextInt(max);
			
		// Return the array.
		return array;
	}
	
	// Prints out all the values in array in the order in which they are
	// stored on a single line and advances to the next line.
	public static void printArray(int[] array) {
		
		for (int i=0; i<array.length; i++)
			System.out.print(array[i]+" ");
		System.out.println();
	}
	
	// If searchVal is contained in values, an index in which it is 
	// contained is returned. Otherwise, -1 is returned.
	public static int binarySearch(int[] values, int searchVal) {
		
		// Set up our search space.
		int low = 0;
		int high = values.length-1;
		
		// Continue so long as there is a search space.
		while (low <= high) {
			
			// The middle index where we want to look.
			int mid = (low+high)/2;
			
			// Our value is smaller than this one.
			if (searchVal < values[mid])
				high = mid-1;
				
			// Our value is bigger than this one.
			else if (searchVal > values[mid])
				low = mid+1;
				
			// We found it!
			else
				return mid;
		}
		
		// If we get here, the value is NOT in the array.
		return NOT_FOUND;
	}
}