基礎知識
順序查找（Sequential Search）：從表中最後一個記錄（或是第一個記錄）開始，逐個進行記錄的關鍵字和給定值的比較。若某個記錄的關鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，若直至第一個記錄（或最後一個記錄），其關鍵字與給定值比較都不等，則表明表中沒有所查記錄，則查找不成功。
折半查找（Binary Search）：折半查找是對有序表的查找中一種最常用的方法。它的查找過程先确定待查記錄所在的範圍（區間），然後逐漸縮小範圍直到找到或找不到該記錄為止。
已知有如下11個資料元素的有序表（關鍵字即為資料元素的值）：
（5，13，19，21，37，56，64，75，80，88，92）
使用折半查找來查找key=21的過程如圖（1）所示，假設指針low和指針high分别訓示待查元素所在範圍的下界與上界，指針mid訓示區間的中間位置，即mid =（low + high）/2。此例中假設用數組存儲上述資料元素，則low和high的初始值分别為0和10，即[0,10]為待查區間，mid初始值為（0+10）/2=5，如圖（1）①所示。此時指針mid所指資料元素為56，大于21，則說明待查元素若存在，必在區間[low，mid-1]範圍内，即[0，4]内，則令high指向mid-1，即下标為4的元素mid=（0+4）/2=2，如圖（1）②所示。此時指針mid所指資料元素為19，小于21，則說明待查元素若存在，必在區間[mid+1，high]範圍内，即[3，4]内，則令low指向mid+1，即下标為3的元素，此時mid=（3+4）/2=3，如圖（1）③所示。此時指針mid所指元素為21，與待查找的元素21相等，查找成功。
再看使用折半查找來查找key=85的過程如（2）所示，low、high、mid的初始值同上，如圖（2）①。此時指針mid所指資料元素為56，小于85，則說明待查元素若存在，必在區間[mid+1，high]範圍内，即[6，10]内，則令low指向mid+1，即下标為6的元素，此時mid=（6+10）/2=8，如圖（2）②所示。此時指針mid所指資料元素為80，小于85，則說明待查元素若存在，必在區間[mid+1，high]範圍内，即[9，10]内，則令low指向mid+1，即下标為9的元素，此時mid=（9+10）/2=9，如圖（2）③所示。此時指針mid所指資料元素為88，大于85，則說明待查元素若存在，必在區間[low，mid-1]範圍内，即[9，8]内，此區間不存在，說明查找失敗，如圖（2）④所示。
由上可知，折半查找過程是以處于區間中間位置記錄的關鍵字和給定值進行比較，若相等，則查找成功；若不相等，則縮小範圍，直至新的區間中間位置記錄的關鍵字等于給定值或者查找區間的大小小于0（表明查找不成功）為止。
代碼實作
順序查找的實作非常簡單，其實作如下：
折半查找算法有遞歸實作及非遞歸實作兩種方法，其實作分别如下：
代碼清單
在算法的測試中，我使用了随機數函數來産生測試資料并儲存在檔案中，再從檔案中讀取資料進行測試，過程較為麻煩。自己實作時可自行設計測試方法。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX_SIZE 10
/***************順序查找********************/
int Search_Seg(int* array,int key)
{
//從最後一個元素往前進行順序查找.
//若找到，則傳回元素下标;若未找到，則傳回-1。
int i;
for(i=MAX_SIZE-1;i>=0;i--)
if(array[i]==key)
return i;
return i;
}
/***************折半查找的遞歸實作************/
int Search_Bin_Recursion(int* array,int key,int start,int end)
{
//在數組array下标為[start,end]區間中查找關鍵字為key的元素.
//若找到，則傳回元素下标;若未找到，則傳回-1。
if(start<=end)
{
int mid=(start+end)/2;
if(array[mid]==key)//找到待查元素
return mid;
else if(array[mid]>key)
return Search_Bin_Recursion(array,key,start,mid-1);//遞歸調用折半查找函數，繼續在前半區間進行查找
else
return Search_Bin_Recursion(array,key,mid+1,end);//遞歸調用折半查找函數，繼續在後半區間進行查找
}
return -1;
}
/**************折半查找的非遞歸實作***********/
int Search_Bin_nonRecursion(int* array,int key)
{
//在數組array中查找關鍵字為key的元素.
//若找到，則傳回元素下标;若未找到，則傳回-1。
int low=0,high=MAX_SIZE-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;
}
/*************選擇排序**************/
void sort(int* array)
{
int i,j,minNo;
for(i=0;i<MAX_SIZE-1;i++)
{
minNo=i;
for(j=i+1;j<MAX_SIZE;j++)
if(array[minNo]>array[j])
minNo=j;
if(minNo!=i)
{
int t=array[i];
array[i]=array[minNo];
array[minNo]=t;
}
}
}
int main()
{
srand((unsigned)time(NULL));//以時間作為随機數種子
int i=0,key,n;
int array[MAX_SIZE];
/**************随機産生測試資料，将産生的随機數寫入檔案*************/
FILE *in=fopen("datafile.txt","w");
if(in==NULL)
{
printf("Open file erroe!\n");
exit(0);
}
while(!feof(in)&&i!=MAX_SIZE)
{
fprintf(in,"%d ",rand()%100);//以時間為種子産生100以内的随機數
i++;
}
fclose(in);//注意别忘記
/**************從檔案中讀取測試資料到數組中********************/
i=0;//将i重置為0
FILE *out=fopen("datafile.txt","r");
if(out==NULL)
{
printf("Open file error!\n");
exit(0);
}
while(!feof(out)&&(i!=MAX_SIZE))
{
fscanf(out,"%d",&array[i]);
i++;
}
fclose(out);
printf("檔案中的随機數為:");
for(i=0;i<MAX_SIZE;i++)
printf("%d ",array[i]);
printf("\n");
printf("---------------測試順序查找-------------------\n");
printf("請輸入需要查找的元素:");
scanf("%d",&key);
n=Search_Seg(array,key);
if(n==-1)
printf("查找失敗。\n\n");
else
printf("查找成功，查找元素的下标為%d。\n\n",n);
sort(array);//折半查找前先對數組進行排序
printf("排序後的随機數為:");
for(i=0;i<MAX_SIZE;i++)
printf("%d ",array[i]);
printf("\n");
printf("---------------測試遞歸折半查找---------------\n");
printf("請輸入需要查找的元素:");
scanf("%d",&key);
n=Search_Bin_Recursion(array,key,0,MAX_SIZE-1);
if(n==-1)
printf("查找失敗。\n\n");
else
printf("查找成功，查找元素的下标為%d。\n\n",n);
printf("---------------測試非遞歸折半查找-----------------\n");
printf("請輸入需要查找的元素:");
scanf("%d",&key);
n=Search_Bin_nonRecursion(array,key);
if(n==-1)
printf("查找失敗。\n");
else
printf("查找成功，查找元素的下标為%d。\n",n);
return 0;
}
運作結果：