import java.util.Random;


public class SearchExample {
	public static final int[] SORTED_SEARCH_SPACE = new int[] {-4, -1, 4, 52, 79, 152, 182, 304, 454, 8954, 98248, 796569};
	
	public static void main(String[] args) {
		Random random = new Random();
		
		int index = Math.abs(random.nextInt() % SORTED_SEARCH_SPACE.length);
		int resultLinear = doLinearSearch(SORTED_SEARCH_SPACE, SORTED_SEARCH_SPACE[index]);

		int resultBinary = doBinarySearch(SORTED_SEARCH_SPACE, SORTED_SEARCH_SPACE[index], 0, SORTED_SEARCH_SPACE.length - 1, 0);
		
		System.out.println("Looking for num " + SORTED_SEARCH_SPACE[index] + " at index " + index + " out of " + SORTED_SEARCH_SPACE.length);
		System.out.println("Linear search took " + resultLinear + " comparisons");
		System.out.println("Binary search took " + resultBinary + " comparisons");
	}
	
	public static int doLinearSearch(int[] space, int target) {
		for (int i = 0; i < space.length; i++) {
			if (space[i] == target) {
				return i + 1;
			}
		}
		return space.length;
	}
	
	// Note: this just counts comparisons and does not return the index where the item is located.
	public static int doBinarySearch(int[] space, int target, int start, int end, int numComparisons) {
		if (start > end) {
			return numComparisons;
		} 
		int midpoint = (start + end) / 2;
		if (space[midpoint] == target) {
			return numComparisons + 1;
		} else if (target < space[midpoint]) {
			return doBinarySearch(space, target, start, midpoint - 1, numComparisons + 1);
		} else {
			return doBinarySearch(space, target, midpoint + 1, end, numComparisons + 1);
		}
	}
}