/*	
	Mr. Bui
	10/4/06
	This program sorts an array and then searches for a number using binary search
*/

import java.io.*;

public class BinarySearch
{
	private static BufferedReader stdin = new BufferedReader( new InputStreamReader( System.in ) );
	
	public static void main(String [] args) throws IOException
	{
		int [] intArray = { 1, 2, 3, 4, 5, 1, 6, 42, 4, 6 ,3, 4, 2, 6, 7, 
			6, 4, 63, 12, 4, 7, 4, 2, 1, 3, 5, 7, 8, 7, 32, 56, 5, 35, 10 }; 
			
		int front = 0; 	// stores the index of the current front/top of the array
		int pos = 0;	//stores the index of the current position in the array
		
		//print the list
		System.out.println("THE UNSORTED ARRAY: ");
		for(int i = 0; i < intArray.length; i++)
		{
			System.out.print(intArray[i] + " ");
		}
		System.out.println();
		
		//SORT THE LIST
		//Create a for loop that uses "front" to iterate from 0 (zero) to the end of the array
		for (front = 0; front < intArray.length; front++)
		{
			//Create a nested for loop that uses "pos" to iterate from the end of the array down to "front"
			for (pos = intArray.length-1; pos > front; pos--)
			{
				//check to see if the element at "pos" is less than the adjacent element
				if (intArray[pos] < intArray[pos-1])
				{
					//swap the elements if the "pos" element is smaller
					int tmp = intArray[pos];
					intArray[pos] = intArray[pos-1];
					intArray[pos-1] = tmp;
				}
			}
		}
		
		//print out the entire array
		System.out.println("THE SORTED ARRAY: ");
		for(int i = 0; i < intArray.length; i++)
		{
			System.out.print(intArray[i] + " ");
		}
		System.out.println();
		
		//BEGINNING OF BINARY SEARCH CODE
		System.out.print("Please enter a number: ");
		int key = Integer.parseInt(stdin.readLine());
		
		int first = 0;
		int last = intArray.length-1;;
		int mid = 0;
		boolean found = false;
		
		while( (!found) && (first <= last) )
		{
			mid = (first + last) / 2;
		
			if(key == intArray[mid]) 
			{
				found = true;
			}
			if(key < intArray[mid])
			{
				last = mid - 1;
			}
			if(key > intArray[mid]) 
			{
				first = mid + 1;
			}
		}
		
		if (found)
		{
			System.out.println(key + " was FOUND!");
		}
		else
		{
			System.out.println(key + " was NOT FOUND!");
		}

	}
}