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

import java.io.*;

public class StringBinarySearch
{
	private static BufferedReader stdin = new BufferedReader( 
		new InputStreamReader( System.in ) );
	
	public static void main(String [] args) throws IOException
	{
		String [] strArray = { "DIGUS", "VESTY", "XYLODOMO", "CLESTY", "CUNCE", "SCHRENTA", 
			"GORA", "COGEN", "MASOR", "KAKIST", "DEMIUM", "OSCAHRON", "PRONY", "ISOR", 
			"LAMULE", "QUOUNX", "NARBER", "SCRACAL", "TRISM", "UNDFUSIC" }; 
		
		//NOT EVERYTHING BELOW THIS LINE WORKS...FIX IT!
			
		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 at index " + mid);
		}
		else
		{
			System.out.println(key + " was NOT FOUND!");
		}

	}
}