Untitled

class Driver
{
	private static int numComparisons;
	
	public static void main(String[] args)
	{
		
		for (int length = 1; length <= 30; length +=1)
		{
			int[] array = new int[length];
			for (int index = 0; index < length; index +=1)
			{
				array[index] = index;
			}

			double binaryTotal = 0.0;
			double linearTotal = 0.0;
			for (int element = 0; element < length; element +=1)
			{
				binaryTotal += binarySearch(array,element);
				linearTotal += linearSearch(array,element);
			}
			
			double binaryAverage = binaryTotal / length;
			double linearAverage = linearTotal / length;

			System.out.println(length + " " + binaryAverage + " " + linearAverage);
		}
	}


	
	
	public static int linearSearch(int[] array, int element)
	{	
		numComparisons = 0;
		int index = 0;
		while(array.length >= index && !isEqual(array[index],element))
		{
			index += 1;
		}
		return numComparisons;
	}
	
	public static int binarySearch(int[] array, int element)
	{
	
		//-1 on failure
		//index [int] on success.
		numComparisons = 0;
		int left = 0;
		int right = array.length-1;
		int middle = (left + right)/2;
		
		while(left <= right && !isEqual(array[middle],element))
		{
			if(greaterThan(array[middle],element))
			{
				//element is on the left, or lowerhalf
				right = middle-1;
			}
			else
			{
				//Upper, or right half
				left = middle+1;
			}
			middle = (left + right) /2;
		}

		if(isEqual(array[middle],element))
		{
			// I must have found it.
			return numComparisons;
		}
		else
		{
			return numComparisons; //not found :(
		}

	}
	
	public static boolean isEqual(int a, int b)
	{
		numComparisons += 1;
		return a == b;
	}
	public static boolean greaterThan(int a, int b)
	{
		numComparisons += 1;
		return a > b;
	}
	
	
}