Need help in fibonacci search algorithm

Question

I am trying to put java code for fibonacci search with my understanding gained from http://en.wikipedia.org/wiki/Fibonacci_search :

Let k be defined as an element in F, the array of Fibonacci numbers. n = Fm is the array size. If the array size is not a Fibonacci number, let Fm be the smallest number in F that is greater than n.

The array of Fibonacci numbers is defined where Fk+2 = Fk+1 + Fk, when k ≥ 0, F1 = 1, and F0 = 0.

To test whether an item is in the list of ordered numbers, follow these steps:

Set k = m. If k = 0, stop. There is no match; the item is not in the array. Compare the item against element in Fk−1. If the item matches, stop. If the item is less than entry Fk−1, discard the elements from positions Fk−1 + 1 to n. Set k = k − 1 and return to step 2. If the item is greater than entry Fk−1, discard the elements from positions 1 to Fk−1. Renumber the remaining elements from 1 to Fk−2, set k = k − 2, and return to step 2.

The below is my code:

package com.search.demo;

public class FibonacciSearch {

static int[] a = {10,20,30,40,50,60,70,80,90,100};

static int required = 70;
static int m = 2;
static int p = 0;
static int q = 0;


/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    FibonacciSearch fs = new FibonacciSearch();
    fs.findm();
    fibSearch(required);
}

private void findm(){
    //here you have to find Fm which matches size of searching array, or which is close to it.
    int n = a.length;
    int fibCurrent = 1;
    int fibPrev1 = 1;
    int fibPrev2 = 0;

    while(n > fibCurrent){
        fibPrev2 = fibPrev1;
        fibPrev1 = fibCurrent;
        fibCurrent = fibPrev1 + fibPrev2;
        m++;
    }
    p = m-1;
    q = m-2;
}

public static int fibSearch(int no){
    for(;;){

        if(m == 0){
            System.out.println("not found");
            return -1;
        }
        int j = f(p);

        if(no == a[j]){
            System.out.println("found at "+p);
        }else if(no < a[j]){
            m = p;
            p = m - 1;
            q = m - 2;

        }else if(no > a[j]){
            m = q; // as per the step 6..
            p = m-1;
            q = m-2;
        }
    }
    //return m;
}

public static int f(int val){

    if(val == 2 || val == 1 || val == 0){
        return 1;
    }
    return (f(val-1) + f(val-2));
}


}

Please correct me what I am doing wrong, and help me understand it clearly..

I have seen this Fibonacci Search and http://www.cs.utsa.edu/~wagner/CS3343/binsearch/searches.html but I am not able to understand..

Answer 1

while(n > fibCurrent){
                      fibPrev2 = fibPrev1;
                      fibPrev1 = fibCurrent;
                      fibCurrent = fibPrev1 + fibPrev2;
                      m++;
                    }

This part in the findm() function is actually comparing nth fibonacci number but according to algorithm it should be cumulative sum of the fibonacci numbers upto that point. Rather you can search for the element in while loop of findm.

Answer 2

Finally I am able to solve the puzzle, that's stopping me..

I think the below code should help someone who are stuck as I did.

package com.search.demo;

public class FibonacciSearch {

int a[] = {10,20,30,40,50,60,70,80,90,100};
static FibonacciSearch fs;

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    fs = new FibonacciSearch();
    int location = fs.find(70);
    if(location < 0){
        System.out.println("number not found..");
    }else{
        System.out.println("found at location "+location);
    }
}

private int find(int no){
    int n = a.length;
    int m = findFm(n);                  //m = Fm iff n is Fibonacci number else returns Fm+1
    int p = fibSequenceIterative(m-1);  //p = Fm-1, always a fibonacci number
    int q = fibSequenceIterative(m -2); //q = Fm-2, always a fibonacci number

    while(true){
        if(no == a[m]){
            return m;
        }else if (no < a[m]){
            if(q == 0){
                return -(m - 1);// we crossed 0th index in array, number not found.
            }                   
            m = m - q;  //moved to 1 step left towards a fibonacci num
            int tmp = p;//hold this temporarily
            p = q;      //move p to 1 step left into another fibonacci num
            q = tmp - q;//moved q to 1 step left....
        }else if(no > a[m]){
            if(p == 1){
                return -m;//we reached 0th index in array again and number not found..
            }
            m = m + q;
            p = p - q;
            q = q - p;
        }
    }

}

private int findFm(int n){
    int prev = 1;
    int curr = 1;
    int next = 0;

    if(n == 0){
        next = 0;
        return -1;
    }else if(n == 1 || n == 2){
        next = 1;
        return 1;
    }else{
        for(int i = 3; ; i++){
            next = prev + curr;
            prev = curr;
            curr = next;
            System.out.println("prev = "+prev+" curr = "+curr+" next = "+next);
            if(n <= curr){
                System.out.println("n = "+n+" curr = "+curr);
                return i;
            }
        }
        //return -1;//we should not get here..
    }


}

/* Iterative method for printing Fibonacci sequence..*/
private int fibSequenceIterative(int n){
    int prev = 1;
    int curr = 1;
    int next = 0;

    if(n == 0){
        next = 0;
        //return 0;
    }else if(n == 1 || n == 2){
        next = 1;
        //return 1;
    }else{
        for(int i = 3; i <= n; i++){
            next = prev + curr;
            prev = curr;
            curr = next;
        }
        return next;
    }
    return next;
}


}

The bit of code what I am doing wrong is managing the indexes, which does influence the position of dividing the array at an index postion.

the m should be find first, to the value that matches n (size of array). if it doesn't match it should be the next value at which the F(x) will be > n. i.e., in my case size is 10 which doesn't match with any fibonacci number, so the next value in the fibonacci series is 13. and the index of i at which our condition satisfied is F(7) = 13 which is > 10. So m = 7

and now p and q are 2 consecutive fibonacci numbers which always determine the interval at which to divide the array.

read the below:

Take N = 54, so that N+1 = 55 = F[10]. We will be searching the sorted array: A[1], ..., A[54], inclusive. The array indexes are strictly between the two Fibonacci number: 0 < 55. Instead of the midpoint, this search uses the next Fibonacci number down from F[10] = 55, namely F[9] = 34. Instead of dividing the search interval in two, 50% on either side, we divide roughly by the golden ratio, roughly 62% to the left and 38% to the right. If y == A[34], then we've found it. Otherwise we have two smaller intervals to search: 0 to 34 and 34 to 55, not including the endpoints. If you have two successive Fibonacci numbers, it's easy to march backwards using subtraction, so that above, the next number back from 34 is 55 - 34 = 21. We would break up 0 to 34 with a 21 in the middle. The range from 34 to 55 is broken using the next Fibonacci number down: 34 - 21 = 13. The whole interval [34, 55] has length 21, and we go 13 past the start, to 34 + 13 = 47. Notice that this is not a Fibonacci number -- it's the lengths of all the intervals that are.(copied from http://www.cs.utsa.edu/~wagner/CS3343/binsearch/fibsearch.html)