import java.util.Scanner;

public class EnhancedSearch {
	public static int enhancedSearchRecur(int[] input, int searchTerm,
	                                      int low, int high) throws Exception {
		if (low > high) {
			throw new Exception("Item Not Found");
		}
		
		int interval = (high - low) / 3;
		int mid1 = low + interval;
		int mid2 = low + 2*interval;
		
		if (searchTerm < input[mid1]) {
			// Result is in lowest 1/3
			return enhancedSearchRecur(input, searchTerm, low, mid1-1);
		}
		else if (searchTerm > input[mid1] && searchTerm < input[mid2]) {
			// Result is in middle 1/3
			return enhancedSearchRecur(input, searchTerm, mid1+1, mid2-1);
		}
		else if (searchTerm > input[mid2]) {
			// Result is in highest 1/3
			return enhancedSearchRecur(input, searchTerm, mid2+1, high);
		}
		else if (searchTerm == input[mid1]) {
			// mid1 is the result
			return mid1;
		}
		else {
			// mid2 is the result
			return mid2;
		}
	}
	
	// Driver for the recursive function
	public static int enhancedSearch(int[] input, int searchTerm) throws Exception {
		return enhancedSearchRecur(input, searchTerm, 0, input.length);
	}
	
	public static void main(String[] args) {
		int inputArray[] = {1,3,4,5,7,8,10,12,13,14,18,19,20};
		System.out.println("Input Data: {1,3,4,5,7,8,10,12,13,14,18,19,20}");
		System.out.print("Search For? ");
		
		Scanner sc = new Scanner(System.in);
		int searchTerm = sc.nextInt();
		sc.close();
		
		System.out.print("Searching for Item " + searchTerm + "... ");
		
		try {
			int loc = enhancedSearch( inputArray, searchTerm );
			System.out.println("Found it at position " + loc + "!");
		} catch (Exception e) {
			System.out.println("Not found!");
		} 
	}
}