package Sortieralgorithmen;

import java.util.Arrays;
import java.util.Random;

public class TrinaereSuche {

    // find sucht im gesamten Array a nach der Zahl x 
    public static boolean find(int[] a, int x) {
        return find(a, x, 0, a.length-1);
    }
    
    // Rekursive Suche im Teilbereich zwischen 
    // Index left und Index right (jeweils inklusive)
    private static boolean find(int[] a, int x, int left, int right) {
        if (left > right) { return false; }
        if (left == right) { return a[left] == x; }
        if (left == right-1) { return a[left] == x || a[right] == x; }
        
        int count = 1 + (right - left);
        count = count / 3;
        System.out.println("a=" + Arrays.toString(a) + " (Länge: " + a.length + "), left=" + left + ", right=" + right + 
                "\nBereiche haben " + ((left+count) - (left) + 1) + ", " + 
                ((right) - (right-count) + 1) + (right-left==2 ? "(NEU: " + (1) + " (weil right-left=2))" : "") + ", " + 
                ((right-(1+count)) - (left+count+1) + 1)  + " = " + (right-left+1) + " Elemente."
                + "\n fix:" + (left) + "-" + (left+count) + ", 2.:" + (right - count) + 
                (right-left==2 ? "(NEUE LÖSUNG: " + right + " (weil right-left=2))" : "") + "-" + right 
                + ", 3.:" + (left + count + 1) + "-" + (right - (1 + count)) + "\n");
        
        int compare = a[left + count];
        if (x <= compare) {
            return find(a, x, left, left + count);
        }
        compare = a[right - count];
        if (x >= compare) {
            return find(a, x, right-left==2 ? right : right - count, right);
        }
        return find(a, x, left + count + 1, right - (1 + count));
    }

    public static void main(String[] args) {
        Random r = new Random();
        int size = 10+r.nextInt(10);
        int a[] = new int[size];
        a[0] = r.nextInt(20)*(r.nextBoolean() ? -1 : 1);
        for (int i = 1; i < size; i++) {
            a[i] = a[i-1] + r.nextInt(10);
        }
        
        for (int i = 0; i < size; i++) {
            if (!find(a, a[i])) {
                System.out.println("Could not find " + a[i]);
            }
        } 
    }
}