int Sequential_Search2(int *a, int n, int key){int i;a[0] = key;for(i = n; a[i] != a[0]; i–);return i;}
二分查找：又叫折半查找，算法简单，效率高，,ASL = (log以2为底的n+1 ) -1
//二分查找,查找之前需要排序int search_Bin(int * array,int len,int key){int low = 0;int high = len -1;while (low <= high){int mid = (low + high) /2 ;if (array[mid] == key){return mid;}else if( array[mid] > key){high = mid – 1;}else{low = mid + 1;}}return -1;}
斐波那契查找：效率高，空间复杂度高，易出错（数组越界）
//斐波那契查找#define MAX_SIZE 30void 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 * array,int len,int key){int low = 0;int high = len -1;int f[MAX_SIZE];fibonacci(f);//创建斐波那契数列int k;for (k = 0; k < MAX_SIZE; k++){//寻找最小匹配的斐波那契数if (f[k] >= len){break;}}for (int i = len; i < f[k]; i++){//补齐不足的位置array[i] = array[high];}while (low <= high){int mid = low + f[k-1] -1;//斐波那契查找效率高，因为在计算机里 加法 比 除法简单.if (key > array[mid]){low = mid + 1;k = k-2;}else if(key < array[mid]){high = mid – 1;k = k – 1;}else{if (mid <= high){//这一步 不懂return mid;}else{return -1;}}}return -1;}斐波那契查找 不是 每次 查找 表长的 一半，而是 用 某个 斐波那契数 分割 表。斐波那契比 二分查找 效率高 是因为 二分 查找 在计算 mid时用的是除法：int mid = (low + high) /2 ;而 斐波那契 用 的是 加法：int mid = low + f[k-1] -1; 但是 斐波那契算法 需要 表长 必须为 某个斐波那契数 -1，，所以 需要 表要 留有一些空间。
插值 查找：当我们 在 字典里 查找 “apple”时，我们 并不会从 打开字典的一半进行查找，而是从 前面开始查找。当我们 查找“zero”时，我们从 尾部开始查找。 这就是 插值查找 和 二分查找的区别。他会 根据 key值 在 表里 的 比例 来 安排 查找的 位置；
插值 查找，与二分查找，代码 仅 一句 不同：
int mid = low + (high-low)*((key-array[low])/(array[high]-array[low]));//根二分查找仅此区别
//插值查找//顺序表+ 均匀分布int insertValue_Search(int * array,int len,int key){int low = 0;int high = len -1;while (low <= high){//根据比例查找int mid = low + (high-low)*((key-array[low])/(array[high]-array[low]));//根二分查找仅此区别int midValue = array[mid];if (midValue > key){high = mid -1;}else if(midValue < key){low = mid +1;}else{return mid;}}return -1;}
总结：
折半查找进行加法与除法运算（mid = (low + high) / 2）,插值查找进行复杂的四则运算( mid = low + (key – a[low] / (a[high] – a[low]) * (high – low)) )，斐波那契查找只是运用简单家减法运算 (mid = low + f[k-1] -1) ，在海量的数据查找过程中，这种席位的差别会影响最终的查找效率。三种有序表的查找本质上是分割点的选择不同，各有优劣，实际开发可根据数据的特点综合考虑再做决定。
完整源代码网盘地址：点击打开链接
一个人的心胸宽阔，可以容不能容的事，可以赢难以赢的人。
