//izziv 1
public class Izziv1 {

    private static int[] generateTable(int n){
        int[] tabela = new int[n];
        for (int i = 1; i<n; i++){
            tabela[i] = i;
        }
        return tabela;

    }
    private static int findLinear(int[] a, int v){
        int velikost = a.length;
        for (int i = 0; i <= velikost; i++ ){
            if(a[i] == v){
                return i;
            }

        }
        return -1;

    }
    //@SuppressWarnings("unused")
    private static int findBinary(int[] a, int l, int r, int v){
        // a == tabela, l == start, r == end, v == searched number
        int sredina = (l + r) / 2;
        if (l<r){
            return -1;
        }
        if(v == a[sredina]){
            return sredina;
        } else if(v <a[sredina]){
            return findBinary(a, l, sredina - 1, v);
        }else {
            return findBinary(a, sredina + 1, r, v);
        }

    }

    private static long timeLinear (int n){
        int[] tableLinear = generateTable(n);

        long startTime = System.nanoTime();
        int randomNumber = (int)(Math.random()*n+1);
        findLinear(tableLinear, randomNumber);
        long endTime = System.nanoTime() - startTime;
        return endTime;

    }
    private static long timeBinary (int n){
        int[] tableBinary = generateTable(n);

        long startTime = System.nanoTime();
        int randomNumber = (int)(Math.random()*n+1);
        findBinary(tableBinary, 1, tableBinary.length, randomNumber);
        long endTime = System.nanoTime() - startTime;
        return endTime;

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //int n = 1000;
        System.out.printf("n   Linearno   Dvojiško\n");
        for (int i = 1000; i <= 100000; i+=1000){
            System.out.printf("%d | %d | %d\n", i, timeLinear(i), timeBinary(i));
        }

    }

}

/*če gre pr binarnem iskanju, na primer tko da iščemo element 13 v tabeli s 7 elementi pride do neskladja in pol vrnemo
 * -1.
 */