待查找的表是有序排列的
解决的方法1：
折半查找/二分法查找
其中线性表采用的是顺序存储
//C int Binary_Search(int *a,int n,int key) { int low,high,mid; //边界的界定 low=1; high=n; while(low<=high) { mid=(low+high)/2 if(key<a[mid])//待查的数小于中间的值，说明数据在待查表的左边 high=mid-1; else if(key>a[mid])//待查的数大于中间的值，说明数据在待查表的右边 low=mid+1; else return mid } return 0; }
算法复杂度分析
时间复杂度：O(log(n)) 每次划分为一半 故 2^x=n 则x=log2（n）
空间复杂度：O（1）
解决的方法2：
插值查找
二分法查找mid=（low+high）/2=low+1/2(high-low)
其中的1/2修改为(key-a[low])/(a[high]-a[low])
mid=low+(key-a[low])/(a[high]-a[low])(high-low)
依据查找的关键字key和查找表中最大最小关键字比较后的查找方法
表长较大，关键字分布比较均匀的查找表，效果比二分法好
解决方法3：
斐波那契查找
斐波那契数列
采用了黄金分割点而不是一分为二
斐波那契数列 F={0,1,1,2,3,5,8,13,21，...........}
a为待查找的数组，例如：a={0,1,16,24,35,47,59,62,73,88,99}
n=10为数组的长度
假设查找的key=59
步骤：
1）边界确定
2）待查数组按照斐波那契数列扩充
3）循环的判断为low<=high
其中的high为原来的待查数组长度，为什么不是扩充后的长度，原因是扩充后的值都是重复原来待查数组的末尾值，在low>n之前已经找到查找的值，否则找不到
那么扩充待查数组长度的目的是：防止查找后半部分的数时没有值
4）查找过程
待查数组：元素F(k)-1个，因为已经从原来的n个扩充为F(k)-1个
分割点划分：
由斐波那契数列的特性：F[k]=F[k-1]+F[k-2]，构建如下的划分
这张图里的high是扩充的F(k)-1而不是n
//C /*构造一个斐波那契数组*/ void Fibonacci(int * F) { F[0]=0; F[1]=1; for(int i=2;i<max_size;++i) F[i]=F[i-1]+F[i-2]; } int Fibonacci_Search(int *a, int n, int key) { int low, high,mid,i,k; low=1;//左边界 high=n;//右边界 int F[n]; Fibonacci(F);//构造一个斐波那契数组F k=0; while(n>F[k]-1)//计算n位于斐波那契数列的位置 k++; for(i=n;i<F[k]-1;i++)//将待查数组长度不满（斐波那契数列中对应值--长度）的数值部分补全 ，也即是在a数组的尾部拷贝补充到指定F[k]-1长度 a[i]=a[n]; while(low<=high) { mid=low+F[k-1]-1;//计算当前分隔的下标 if(key<a[mid])//若查找记录小于当前分隔记录，说明key在待查数组的前半部分 { high=mid-1;//最高下标调整到分隔下标mid-1处 k=k-1;//斐波那契数列的下标减1位 } else if(key>a[mid])//若查找记录大于当前分隔记录，说明key在待查数组的后半部分 { low=mid+1; k=k-2; } else { if(mid<=n)//若相等且小于长度n则说明mid为查找到的位置 return mid; else//若mid>n说明是补全数值，返回待查数组的末尾的第一个数字索引n return n ; } } return -1; }
时间复杂度: O（logn）
空间复杂度: O(n) 斐波那契数列的创建
可参考：
斐波那契查找原理详解与实现https://www.cnblogs.com/bethunebtj/p/4839576.html
《大话数据结构》
