我們如果僅僅是把書整理在書架上，要找到一本書還是比較困難的，也就是用8.2節的順序查找表，但如果我們在整理書架時，將圖書按書名的拼音排序放置，那麼要找到一本書就相對容易了。簡單的說，就是對圖書做了有序排列，一個線性表有序時，對於查找總是很有幫助的。
8.3.1折半查找
折半查找：又叫二分查找binary search)。它的前提是線性表中的記錄必須是關鍵碼有序通常從小到大），線性表必須采用順序存儲。折半查找的基本思想：在有序表中，選中間記錄作為比較對象，若給定值與中間記錄的關鍵字相等，則查找成功；若給定值小於中間記錄的關鍵字，則在中間記錄的左半區繼續查找；若給定值大於中間記錄的關鍵字，則在中間記錄的右半區繼續查找。不斷重復上述過程，直到查找成功，或所有的查找區域無記錄，查找失敗。
#include <stdio.h>
#include <stdlib.h>
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])
high = mid - 1;
else if(key>a[mid])
low = mid + 1;
else
return 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 <stdio.h>
#include <stdlib.h>
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<F[k]-1;i++)
a[i] = a[n-1];
while(low<=high)
{
mid = low + F[k-1] - 1;
if(key<a[mid])
{
high = mid - 1;
k = k - 1;
}
else if(key>a[mid])
{
low = mid + 1;
k = k - 2;
}
else
{
if(mid < n-1)
return mid;
else
return 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;//加法
斐波那契算法效率高。
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1282331
