本文主要是介绍斐波拉契查找及二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
斐波拉契查找
代码
#include <stdio.h>
#include <stdlib.h>//求第n项的斐波拉契数
int fib(n) {int left = 0;int right = 1;while ( --n > 0 ) {right = left + right;left = right - left;} return right;
}//求n个斐波拉契数
int * fibList(n) {int *a = calloc(sizeof(int), n);for (int i = 0; i < n; i++) {a[i] = fib(i+1);}return a;
}int fibSearch(int *a, int size,int search) {int mid, low = 0, high = size-1;int *p = fibList(high-low);while(low < high) {int i = 0;while (high - low >= p[i]) { //查找符合的斐波拉契数i++;}mid = low + p[i-1] -1; //构造一个中点printf("low=%d,high=%d\n", low, high);printf("p[%d]=%d,mid=%d,a[mid]=%d\n", i-1, p[i-1], mid, a[mid]);if ( search < a[mid] ) {high = mid;} else if (a[mid] < search) {low = mid+1;} else {return mid;}}return -1;
}int main() {int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};printf("%d\n", fibSearch(a, 10, 7));
}
执行过程
low=0,high=9
p[5]=8,mid=7,a[mid]=8
low=0,high=7
p[4]=5,mid=4,a[mid]=5
low=5,high=7
p[2]=2,mid=6,a[mid]=7
6
二分查找
代码
int binSearch(int *a, int size, int search) {int mid, low = 0, high = size-1;while (low < high) {mid = (low + high) >> 1;if ( search < a[mid] ) {high = mid;} else if (a[mid] < search) {low = mid + 1;} else {return mid;}}return -1;
}
说明：斐波拉契查找要优于二分查找，如上代码每次二分查找的时候向左边查找的比较次数是1，向右边查找比较次数为2。故而我们期望查找区间多落在左侧区间，少落在右侧区间，为了找到那个合适的点，最终推论出了斐波拉契的那个点（即是黄金分割点）。故而有了斐波拉契查能性能优于二分查找。
资料：https://www.bilibili.com/video/BV1db411L71m?p=56
这篇关于斐波拉契查找及二分查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
