/*
Informatik II, SS 2001
Übungsblatt 6, Aufgabe 1
Musterlösung.
Interpolationssuche
*/

import java.io.*;

public class InterpolationSearch {
	// Gibt die Position des Elements zurück (bei 0 beginnend),
	// wenn es vorhanden ist, -1, wenn nicht.
    private static int search (int[] a, int l, int r, int k) {
		if (a[l] == k) 
			return l;
		else if ((l == r) || (a[l] == a[r]))
			return -1;
		else {
			// Position des Elements abschätzen.
			float next_guess = l + ((k - a[l]) * (float)(r - l) / (float)(a[r] - a[l]));
			int m = (int)Math.ceil(next_guess);	  // aufrunden.		
			if (m > r) return -1;
			if (k < a[m])
				return search(a, l, m - 1, k);
			else
				return search(a, m, r, k);
		}
    }
    
	public static void main (String[] args) throws IOException {
		int[] a = {2, 5, 6, 9, 13, 18, 21, 26, 27, 35, 38, 44, 45, 55, 60, 66};
		System.out.print("Liste: ");
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
		System.out.print("Geben Sie eine ganze Zahl ein: ");
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		int k = Integer.parseInt(kb.readLine());
		// Element ist kleiner als das erste oder größer als das letzte.
		if ( (k < a[0]) || (k > a[a.length - 1]) )
			System.out.println("Das Element " + k + " ist nicht vorhanden.");
		// sonst suchen.
		else {
			int s = search(a, 0, a.length - 1, k);
			if (s != -1) 
				System.out.println("Das Element " + k + " ist an Position: " + s);
			else
				System.out.println("Das Element " + k + " ist nicht vorhanden.");
		}
    }
}