import java.util.Random;

public class suchen {

	public static void main(String[] args)
	{
		//int
		int länge = 10;
		int key = 4;
		int feld[] = new int[länge];
		erzeugen(feld, 10);
		quicksort_rechts_Pivot(feld, 0, feld.length-1);
		ausgeben(feld);
		int erg = lineareSuche(feld, key);
		System.out.println("Zu suchen ist :" + key );
		System.out.println("lineare Suche :" + erg);
		int temp = runBinarySearchIteratively(feld, key, 0, feld.length-1);
		System.out.println("Binäre Suche  :" + temp);

		System.out.println();
		System.out.println("String");
		System.out.println();

		//Strings
		String key2 = "abc";
		int length = 10;
		String arr [] = new String[length];
		erzeugen(length, arr);
//		arr[0] = "abc";
		ausgeben(arr);
		quicksort(arr, 0, arr.length-1);
		ausgeben(arr);
		int temp2 = linSuche2(arr, key2);
		int temp3 = binareSucheIte(arr, key2);
		System.out.println("Zu suchen ist :" + key2 );
		System.out.println("lineare Suche :" + temp2);
		System.out.println("Binäre Suche  :" + temp3);
	}

	static public void erzeugen(int[] feld, int max)
	{
		Random r = new Random();
		for(int i = 0; i < feld.length;++i)
		{
			feld[i] = r.nextInt(max)+1;
		}
	}

	static public void ausgeben(int[] feld)
	{
		for(int i = 0; i < feld.length;++i)
		{
			System.out.print(feld[i] + " ");
		}
		System.out.println();
	}

	static void quicksort_rechts_Pivot(int a[], int l, int r)
	{
		int v, i, j , t;

		if (r > l)
		{
			v = a[r];
			i = l-1;
			j = r;
			for (;;)
			{
				while (a[++i] < v) ;
				while (j > 0 && a[--j] > v) ;
				if (i >= j)
					break;
				t = a[i];
				a[i] = a[j];
				a[j] = t;
			}
			t = a[i];
			a[i] = a[r];
			a[r] = t;
			quicksort_rechts_Pivot(a, l, i-1);
			quicksort_rechts_Pivot(a, i+1, r);
		}
	}

	static int lineareSuche(int [] arr,int zahl)
	{
		for(int i = 0; i< arr.length; ++i)
		{
			if(arr[i] == zahl)
				return i;
		}
		return -1;
	}

	static public int runBinarySearchIteratively(int[] sortedArray, int key, int links, int rechts)
	{
		while (links <= rechts)
		{
			int mid = (links + rechts) / 2;
			if (sortedArray[mid] < key)
			{
				// If key is greater, ignore left half
				links = mid + 1;
			} else if (sortedArray[mid] > key)
			{
				// If key is smaller, ignore right half
				rechts = mid - 1;
			} else if (sortedArray[mid] == key)
			{
				// Check if key is present at mid
				return mid;
			}
		}
		return -1;
	}

	static int binarySearch(int arr[], int links, int rechts, int key)
	{
		if(links > rechts)
			return -1;

		int mid = (links +rechts )/ 2;
		if(arr[mid] == key)
			return mid;
		else if(key < arr[mid])
			return binarySearch(arr,links, mid-1, key);
		else
			return binarySearch(arr,mid +1, rechts, key);
	}


	//	String Suche
	static String allowedChars ="0123456789abcdefghijklmnopqrstuvwxyz";

	private static String generateRandomString(String allowedChars, Random random, int laenge)
	{
		int max = allowedChars.length();
		StringBuffer buffer = new StringBuffer();
		for (int i=0; i<laenge; i++)
		{
			int value = random.nextInt(max);
			buffer.append(allowedChars.charAt(value));
		}
		return buffer.toString();
	}

	static public void erzeugen(int stringlaenge,String[] arr)
	{
		Random random = new Random();
		for (int i=0; i<arr.length; i++)
		{
			arr[i] = generateRandomString(allowedChars, random, stringlaenge);
		}
	}

	static public void ausgeben(String[] arr)
	{
		for(int i = 0; i < arr.length;++i)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	static public int linSuche2(String[] feld, String a)
	{
		for (int i=0; i<feld.length; i++)
		{
			if (a.equals(feld[i]))
			{
				return i;
			}
		}
		return -1;
	}

	static public int binareSucheIte(String[] feld, String gzahl)
	{
		int links = 0;
		int rechts = feld.length-1;
		int mitte;
		while(links<=rechts)
		{
			mitte = (links+rechts)/2;

			if(feld[mitte].equals(gzahl))
			{
				return mitte;
			}

			if(feld[mitte].compareTo(gzahl)>0)
			{
				rechts = mitte-1;
			}
			else
			{
				links = mitte+1;
			}
		}
		return -1;
	}

	static int binarySearch(String arr[], int links, int rechts, String key)
	{
		if(links > rechts)
			return -1;

		int mid = (links + rechts )/ 2;
		if(arr[mid].equals(key))
			return mid;
		else if(key.compareTo(arr[mid]) < 0)
			return binarySearch(arr,links, mid-1, key);
		else
			return binarySearch(arr,mid +1, rechts, key);
	}

	static void quicksort(String a[], int l, int r)
	{
		// v: v ist das Pivot-Element
		// i: i läuft von links nach rechts (Laufindex)
		// j: j läuft von rechts nach links (Laufindex)
		String v;
		int i, j;
		// Solange die rechte Grenze größer ist als die linke
		if (r>l)
		{
			// die rechte Grenze wird als Pivot-Element gesetzt
			v = a[r];
			// i wird auf eins weniger als die linke Grenze gesetzt
			i=l-1;
			// j wird auf die rechte Grenze gesetzt
			j=r;
			// endlos Schleife, wartet auf ein break
			for(;;)
			{
				// sucht das nächste Element sodass a[i] > v
				while (a[++i].compareTo(v) < 0);
				// sucht das nächste Element sodass a[j] < v
				// j > 0 ist notwendig, weil sonst j negativ werden kann
				while (j > 0 && a[--j].compareTo(v) > 0);
				// Abfrage nach Überkreuzung
				if (i>=j) break;
				// Wenn keine Überkreuzung stattgefunden hat,
				// wird a[i] mit a[j] getauscht
				swap(a,i,j);
			}
			// das Pivot-Element wird an die richtige
			// Stelle gebracht
			swap(a,i,r);
			// rekursiver Aufruf für linkes und rechtes
			// Subarray, Element an Addresse i bleibt
			// unverändert
			quicksort (a,l, i-1);
			quicksort(a,i+1,r);
		}
	}

	public static void swap(String[] arr, int a, int b)
	{
		String temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}