chapter1/section4/Exercise22_BinarySearchAddSub.java about algorithms-sedgewick-wayne HOT 10 CLOSED

//searched through the whole array but not found
if (elementToCheck == 0 || elementToCheck == array.length-1) {
    return -1;
}

// Based on http://algs4.cs.princeton.edu/14analysis/:
// Answer: Instead of searching based on powers of two (binary search),
// use Fibonacci numbers (which also grow exponentially).
// Maintain the current search range to be [i, i + F(k)] and keep F(k), F(k-1) in two variables.
// At each step compute F(k-2) via subtraction, check element i + F(k-2),
// and update the range to either [i, i + F(k-2)] or [i + F(k-2), i + F(k-2) + F(k-1)].

if (key < array[elementToCheck]) {
    high = low + fibonacciBeforeN;
}

if (key < array[elementToCheck]) {
    high = low + fibonacciBeforeN;

    aux = fibonacciBeforeN;
    fibonacciBeforeN = fibonacciN - fibonacciBeforeN; // F(k-2)
    fibonacciN = aux; // F(k-1)
}

private int binarySearch(int[] array, int key) {
    int aux;
    int fibonacciBeforeN = 0;
    int fibonacciN = 1;

    // Compute F(k)
    while (fibonacciN < array.length - 1) {
        aux = fibonacciN;
        fibonacciN = fibonacciBeforeN + fibonacciN;
        fibonacciBeforeN = aux;
    }

    int low = 0;
    int high = low + array.length - 1;

    while (low <= high) {
        if (fibonacciBeforeN > 0) {
            // Compute F(k-2)
            aux = fibonacciBeforeN;
            fibonacciBeforeN = fibonacciN - fibonacciBeforeN; // F(k-2)
            fibonacciN = aux; // F(k-1)
        }

        int elementToCheck = low + fibonacciBeforeN;
        if (elementToCheck > high) {
            elementToCheck = high;
        }

        if (key < array[elementToCheck]) {
            high = elementToCheck - 1;

            // shrink range one more step
            if (fibonacciBeforeN > 0) {
                // Compute F(k-2)
                aux = fibonacciBeforeN;
                fibonacciBeforeN = fibonacciN - fibonacciBeforeN; // F(k-2)
                fibonacciN = aux; // F(k-1)
            }
        } else if (key > array[elementToCheck]) {
            low = elementToCheck + 1;
        } else {
            return elementToCheck;
        }
    }

    return -1;
}

public static void main(String... args) {
    Exercise22_BinarySearchAddSub exercise22_binarySearchAddSub = new Exercise22_BinarySearchAddSub();

    int N = 30;

    for (int i = 1; i <= N; i++) {
        int[] array = IntStream.iterate(2, e -> e + 2).limit(i).toArray();
        int M = (i << 1) + 1;

        for (int j = 1; j <= M; j++) {
            StdOut.print(Arrays.toString(array));
            int index = exercise22_binarySearchAddSub.binarySearch(array, j);
            StdOut.printf(" KEY: %5d; INDEX: %5d\n", j, index);
        }

        StdOut.println();
    }
}

private int binarySearch(int[] array, int key) {
    int aux;
    int fibonacciBeforeN = 0;
    int fibonacciN = 1;

    // Compute F(k)
    while (fibonacciN < array.length - 1) {
        aux = fibonacciN;
        fibonacciN = fibonacciBeforeN + fibonacciN;
        fibonacciBeforeN = aux;
    }

    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        while (fibonacciBeforeN > 0 && fibonacciN >= high - low) {
            // Compute F(k-2)
            aux = fibonacciBeforeN;
            fibonacciBeforeN = fibonacciN - fibonacciBeforeN; // F(k-2)
            fibonacciN = aux; // F(k-1)
        }

        int elementToCheck = low + fibonacciBeforeN;

        if (key < array[elementToCheck]) {
            high = elementToCheck - 1;
        } else if (key > array[elementToCheck]) {
            low = elementToCheck + 1;
        } else {
            return elementToCheck;
        }
    }

    return -1;
}