/**
 * BinarySearch
 *
 * This class demonstrates a binary search.
 * Binary search examines the middle element first to
 * find the key. If the middle is key, then it returns
 * the subscript of the middle element. If the key is
 * greater than the middle element, then the search divides
 * examines the upper half of the array for the key. If
 * the key is less than the middle element, then the search
 * examines the lower half. BinarySearch follows this algorithm
 * until it finds the key or if the key is not located in
 * the array, it return -1.
 * @author Brad Rippe
 * @version 1.0
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] intArray =  new int[1000];
        int[] intArray2 = new int[10000];

        // fill the arrays
        for(int i=0; i<intArray.length;i++)
            intArray[i] = i+1;

		for(int i=0; i<intArray2.length;i++)
            intArray2[i] = i+1;

        //Search for elements
        System.out.println("Searching intArray for 999");
        System.out.println("Found 999 intArray at position " +
            				binarySearch(intArray, 999));

        System.out.println("Searching intArray for 500");
        System.out.println("Found 500 intArray at position " +
            				binarySearch(intArray, 500));

        System.out.println("Searching intArray for 2");
        System.out.println("Found 2 intArray at position " +
            				binarySearch(intArray, 2));
    }

    public static int binarySearch(int[] array, int key) {
		int low = 0;
        int high = array.length-1;
        int mid;

        while(low <= high) {
            mid = (low + high)/2;

            System.out.println("Examining array for key...");

            if(key == array[mid])
                return mid;				// key found, we're done!
            else if(key > array[mid])
				low = mid+1;			// examine the upper half
            else 						// key < array[mid]
                high = mid-1;			// examine the lower half
        }

        return -1;
    }
}