public class binDemo
{
	public static int binarySearch(int anArray[], int first, int last, int value)
	{
		int index;

		if(first > last)
		{
			index = -1;		//value not in original array
		}
		else
		{
			int mid = (first + last)/2;

			if(value == anArray[mid])
			{
				index = mid;		//value found at anArray[mid]
			}
			else if(value < anArray[mid])
			{
				index = binarySearch(anArray, first, mid-1, value);
			}
			else
			{
				index = binarySearch(anArray, mid+1, last, value);
			}
		}

		return index;
	}

	public static void main(String[] arg)
	{
		//Create a sorted array
		int[] myArray = {0,1,9,13,24,35,46,57,68,79,110,
				111,212,213,314,315,416,417,418,419,520};
		int start = 0;		//indicates the beginning index
		int end = myArray.length;		//indicates the last index

		//locate the following values in the array
		int x = 9;
		int y = 416;
		int z = 75;
		int result;						//result of search

		System.out.println("Searching for " + x);
		try
		{
			result = binarySearch(myArray, start, end, x);
		}
		catch(ArrayIndexOutOfBoundsException e)
		{
			result = -1;
		}

		if(result >= 0)		//value located
			System.out.println("Value " + x + " located at position " + result);
		else
			System.out.println("Value " + x + " not located!");

		System.out.println("Searching for " + y);
		try
		{
			result = binarySearch(myArray, start, end, y);
		}
		catch(ArrayIndexOutOfBoundsException e)
		{
			result = -1;
		}

		if(result >= 0)		//value located
			System.out.println("Value " + y + " located at position " + result);
		else
			System.out.println("Value " + y + " not located!");

		System.out.println("Searching for " + z);
		try
		{
			result = binarySearch(myArray, start, end, z);
		}
		catch(ArrayIndexOutOfBoundsException e)
		{
			result = -1;
		}
		if(result >= 0)		//value located
			System.out.println("Value " + z + " located at position " + result);
		else
			System.out.println("Value " + z + " not located!");
	}
}