|
斐波那契数列我们都知道{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 }，前后的比值会越来越接近0.618，也就是黄金分割点。0.618也被公认为最具有审美意义的比例数字。斐波那契查找原理其实和二分法查找原理差不多，只不过计算中间值mid的方式不同，还有一点就是斐波那契查找的数组长度必须是f（k）-1，这样我们就可以把斐波那契数列进行划分 f(k)-1=f(k-1)+f(k-2)-1=[f(k-1)-1]+1+[f(k-2)-1]；然后前面部分和后面部分都还可以继续进行划分。但实际上我们要查找的数组长度不可能都是f（k）-1，所以我们要补齐最后的部分，让数组的长度等于f（k）-1，让数组的最后一位数字把后面铺满。比如我们查找的数组长度是21，而f（8）-1=21-1=20；小于21，所以f（8）-1是不行的，我们需要把数组长度变为f（9）-1=34-1=33，后面多余的我们都用原数组最后的那个值填充。我们来看下代码 1public static int fibonacciSearch(int[] array, int key) {
2 if (array == null || array.length == 0)
3 return -1;
4 int length = array.length;
5 int k = 0;
6 while (length > fibonacci(k) - 1 || fibonacci(k) - 1 < 5) {
7 k++;
8 }
9 int[] fb = makeFbArray(fibonacci(k) - 1);
10 int[] temp = Arrays.copyOf(array, fb[k] - 1);
11 for (int i = length; i < temp.length; i++) {
12 temp[i] = array[length - 1];//用原数组最后的值填充
13 }
14 int low = 0;
15 int hight = length - 1;
16 while (low <= hight) {
17 int middle = low + fb[k - 1] - 1;
18 if (temp[middle] > key) {//要查找的值在前半部分
19 hight = middle - 1;
20 k = k - 1;
21 } else if (temp[middle] < key) {//要查找的值在后半部分
22 low = middle + 1;
23 k = k - 2;
24 } else {
25 if (middle <= hight) {
26 return middle;
27 } else {
28 return hight;
29 }
30 }
31 }
32 return -1;
33}
34
35private static int fibonacci(int n) {
36 if (n == 0 || n == 1)
37 return n;
38 return fibonacci(n - 1) + fibonacci(n - 2);
39}
40
41public static int[] makeFbArray(int length) {
42 int[] array = new int[length];
43 array[0] = 0;
44 array[1] = 1;
45 for (int i = 2; i < length; i++)
46 array[i] = array[i - 1] + array[i - 2];
47 return array;
48}
其实经过测试发现斐波那契查找效率并没有那么高，我们再来看一下斐波那契查找的递归实现
1public static int search(int[] array, int value) {
2 if (array == null || array.length == 0) return -1;
3 int length = array.length;
4 int k = 0;
5 while (length > fibonacci(k) - 1 || fibonacci(k) - 1 < 5) {
6 k++;
7 }
8 int[] fb = makeFbArray(fibonacci(k) - 1);
9 int[] temp = Arrays.copyOf(array, fb[k] - 1);
10 for (int i = length; i < temp.length; i++) {
11 temp[i] = array[length - 1];//用原数组最后的值填充
12 }
13 return fibonacciSearch(temp, fb, value, 0, length - 1, k);
14}
15
16public static int fibonacciSearch(int[] array, int[] fb, int value, int low, int hight, int k) {
17 if (value < array[low] || value > array[hight] || low > hight) return -1;
18 int middle = low + fb[k - 1] - 1;
19 if (value < array[middle]) {
20 return fibonacciSearch(array, fb, value, low, middle - 1, k - 1);
21 } else if (value > array[middle]) {
22 return fibonacciSearch(array, fb, value, middle + 1, hight, k - 2);
23 } else {
24 if (middle <= hight) {
25 return middle;
26 } else {
27 return hight;
28 }
29 }
30}
31
32private static int fibonacci(int n) {
33 if (n == 0 || n == 1) return n;
34 return fibonacci(n - 1) + fibonacci(n - 2);
35}
36
37public static int[] makeFbArray(int length) {
38 int[] array = new int[length];
39 array[0] = 0;
40 array[1] = 1;
41 for (int i = 2; i < length; i++) array[i] = array[i - 1] + array[i - 2];
42 return array;
43}
上面的两个斐波那契查找有一个缺点，就是数组长度必须是斐波那契数减1，否则数组就要增大，浪费空间。我们可以优化一下，不需要扩大数组的长度，当查找的位置大于原数组的长度的时候，我们让比较的值等于数组的最后一个元素即可。 1public static int fibonacciSearch1(int[] array, int key) {
2 if (array == null || array.length == 0)
3 return -1;
4 int length = array.length;
5 int k = 0;
6 while (length > fibonacci(k) - 1 || fibonacci(k) - 1 < 5) {
7 k++;
8 }
9 int[] fb = makeFbArray(fibonacci(k) - 1);
10 int low = 0;
11 int hight = length - 1;
12 while (low <= hight) {
13 int middle = low + fb[k - 1] - 1;
14 int midvalue;
15 if (middle >= length)
16 midvalue = array[length - 1];
17 else
18 midvalue = array[middle];
19 if (midvalue > key) {//要查找的值在前半部分
20 hight = middle - 1;
21 k = k - 1;
22 } else if (midvalue < key) {//要查找的值在后半部分
23 low = middle + 1;
24 k = k - 2;
25 } else {
26 if (middle <= hight) {
27 return middle;
28 } else {
29 return hight;
30 }
31 }
32 }
33 return -1;
34}
|
