我们如果仅仅是把书整理在书架上，要找到一本书还是比较困难的，也就是用8.2节的顺序查找表，但如果我们在整理书架时，将图书按书名的拼音排序放置，那么要找到一本书就相对容易了。简单的说，就是对图书做了有序排列，一个线性表有序时，对于查找总是很有帮助的。

8.3.1折半查找

折半查找：又叫二分查找（binary search)。它的前提是线性表中的记录必须是关键码有序（通常从小到大），线性表必须采用顺序存储。折半查找的基本思想：在有序表中，选中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有的查找区域无记录，查找失败。

#include 
     
      #include 
      
       int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};int BinarySearch(int *a, int n, int key){int low;int high;int mid;low = 0;high = n - 1;while(low<=high){mid = (low + high)/2;if(key
       
        a[mid])low = mid + 1;elsereturn mid;}return -1;}int main(){int addr;int key = 2;addr = BinarySearch(arr, 10, key);if(addr == -1)printf("查找失败\n");else{printf("查找成功\n");printf("所在位置为：%d\n",addr);}return 0;}
       
      
     

8.3.2插值查找

我们现在的新问题是，为什么一定要折半，而不是四分之一或者折更多呢。

打个比方，在英文词典里查找“apple”，你会下意识的翻到靠前的书页，而不是从字典的中间开始查找。

插值查找：根据关键字key于查找表中最大最小记录的关键字比较后的查找方法。

在折半查找中 mid = (low + high)/2 = low + 1/2(high - low);

插值查找：mid= ((key - a[low])/(a[high] - a[low])) * (high - low); 

8.3.3斐波那契查找

利用黄金分割原理来实现。

斐波那契数列：0 1 1 2 3 5 8 13 21 34 ......

#include 
     
      #include 
      
       int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};int F[10] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34};int FibonacciSearch(int *a, int n, int key){int low;int high;int mid;int i;int k;low = 0;k = 0;high = n - 1;while(n>F[k])k++;for(i=n; i
       
        a[mid]){low = mid + 1;k = k - 2;}else{if(mid < n-1)return mid;elsereturn n-1;}}return -1;}int main(){int addr;int key = 2;addr = FibonacciSearch(arr, 10, key);if(addr == -1)printf("查找失败\n");else{printf("查找成功\n");printf("所在位置为：%d\n",addr);}return 0;}
       
      
     

3种算法的比较

折半查找：mid= (low + high)/2 = low + 1/2(high - low);//加法，乘法

插值查找：mid=low + ((key - a[low])/(a[high] -a[low])) * (high - low); // 乘法、除法。

斐波那契查找：mid = low + F[k] - 1;//加法

斐波那契算法效率高。