and a constant amount of extra memory. The running time of your program should be proportional to log N in the worst case
算法：
package com.frozenxia.algorithm.basic; public class FibonacciSearch { public int min(int a, int b) { return a < b ? a : b; } public int search(int[] arr, int x, int n) { /* Initialize fibonacci numbers */ int fibMMm2 = 0; // (m-2)'th Fibonacci No. int fibMMm1 = 1; // (m-1)'th Fibonacci No. int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci /* * fibM is going to store the smallest Fibonacci Number greater than or * equal to n */ while (fibM < n) { fibMMm2 = fibMMm1; fibMMm1 = fibM; fibM = fibMMm2 + fibMMm1; } // Marks the eliminated range from front int offset = -1; /* * while there are elements to be inspected. Note that we compare * arr[fibMm2] with x. When fibM becomes 1, fibMm2 becomes 0 */ while (fibM > 1) { // Check if fibMm2 is a valid location int i = min(offset + fibMMm2, n - 1); /* * If x is greater than the value at index fibMm2, cut the subarray * array from offset to i */ if (arr[i] < x) { fibM = fibMMm1; fibMMm1 = fibMMm2; fibMMm2 = fibM - fibMMm1; offset = i; } /* * If x is greater than the value at index fibMm2, cut the subarray * after i+1 */ else if (arr[i] > x) { fibM = fibMMm2; fibMMm1 = fibMMm1 - fibMMm2; fibMMm2 = fibM - fibMMm1; } /* element found. return index */ else return i; } /* comparing the last element with x */ if (fibMMm1 != 0 && arr[offset + 1] == x) return offset + 1; /* element not found. return -1 */ return -1; } int fbsearch(int[] arry, int target) { int fm1 = 1; int fm2 = 0; int fm0 = fm1 + fm2; while (fm0 < arry.length) { fm2 = fm1; fm1 = fm0; fm0 = fm1 + fm2; } int offset = -1; while (fm1 > 0) { int mid = min((offset + fm1), arry.length - 1); if (arry[mid] == target) return mid; else if (arry[mid] < target) { fm0 = fm2; fm1 = fm1 - fm2; fm2 = fm2 - fm1; offset = mid; } else { fm0 = fm1; fm1 = fm2; fm2 = fm0 - fm1; } } return -1; } public static void main(String[] args) { int arry[] = new int[100]; for (int i = 0; i < 100; i++) { arry[i] = i + 8; } FibonacciSearch fs = new FibonacciSearch(); for (int i : arry) { // System.out.println(fs.search(arry, i)); // System.out.println(fs.search(arry, i, arry.length)); System.out.println(fs.fbsearch(arry, i)); } // System.out.println(fs.fbsearch(arry, -1887)); } }
Reference：
http://www.geeksforgeeks.org/fibonacci-search/
