二分查找和黄金分割查找效率比较 黄金分割从哪个点计算的

问题引入：

在二分查找中，我们是取mid等于left和right的中间值，即用等分的方法进行查找。

那为什么一定要等分呐？能不能进行“黄金分割”？也就是mid=left+0.618(right-left),当然mid要取整数。如果这样查找，时间复杂性是多少？也许你还可以编程做个试验，比较一下二分法和“黄金分割”法的执行效率。

分析：

由上面的分析，我们可以知道，二分查找和黄金分割查找，它们的时间复杂度量级是一样的，都是O(logN)，比顺序查找要高效得多，但是从最坏时间复杂度上看，二分查找为log2N，黄金分割查找为log1.894N，显然，二分查找是比较高效一些的。那么接下来就用一段代码来区别它们的执行效率。

测试： #include#include#define MAXSIZE 10000000/*clock_t是clock()函数返回的变量类型*/clock_t start,stop;int array[MAXSIZE];/*二分查找和黄金分割查找函数*/int Fun1(int K);int Fun2(int K);/*将函数指针命名为MyFun，要测试运行时间时，只需要传过去被调用的函数名，由Time函数返回时间*/typedef int (*MyFun)(int K);double Time(MyFun Fun); int main(){int K,i;for(i=0;imid=(left+right)/2;if(K>array[mid]) left=mid+1;else if(Kmid=left+0.618*(right-left);if(K>array[mid]) left=mid+1;else if(K