折半查找
如果从文件中读取的数据记录的关键字是有序排列的（递增的或是递减的），则可以用一种更有效率的查找方法来查找文件中的记录，这就是折半查找法，又称为二分搜索。
折半查找的基本思想：减少查找序列的长度，分而治之地进行关键字的查找。他的查找过程是：先确定待查找记录的所在的范围，然后逐渐缩小查找的范围，直至找到该记录为止（也可能查找失败）。例如文件记录的关键字序列为：
　　　　（1，3，5，7，9，11，13，17，21，28，32）
该序列包含11个元素，而且关键字单调递增。现在想查找关键字key为28的记录。如果应用顺序查找法进行查找，需要将28之前的所有关键字与key进行比较，共需10次，如果用折半查找可以这样做：
设指针low和high分别指向关键字序列的上界和下界，即low=0,high=10。指针mid指向序列的中间位置，即mid=[(low+high)/2]=5。在这里low指向关键字1，high指向关键字32，mid指向关键字11。
　　　　（1，3，5，7，9，11，13，17，21，28，32）
　　　　　↑ 　　　　　　　↑　　　　　　　　　　↑
　　　　　low　　　　　　mid　　　　　　　　　high
　(1)首先将mid所指向的元素与key进行比较，因为key=28，大于11，这就是说明待查找的关键字一定位于mid和high之间。这是因为原关键字序列是有序递增的。因此下面的查找工作只需在[mid+1,high]中进行。于是指针low指向mid+1的位置，即low=6,也就是指向关键字13,并将mid调整到指向关键字21，即mid=8。
　　　　（1，3，5，7，9，11，13，17，21，28，32）
　　　　　　　　　　　　　　　↑ 　　　　↑　　　↑
　　　　　　　　　　　　　　　low　　　mid　　high
　(2)再将mid所指向的元素与key进行比较，因为key=28，大于21，说明待查找的关键字一定位于mid和high之间。所以下面的查找工作仍然只需在[mid+1,high]中进行。于是指针low指向mid+1的位置，即low=9，也就是指向关键字28，并将mid调整到指向关键字28，即mid=9。high保持不变。
　（1，3，5，7，9，11，13，17，21，28，32）
　　　　　　　　　　　　　　　 　　　↑　　↑
　　　　　　　　　　　　　　　　　　mid　high
　　　　　　　　　　　　　　　　　　low
(3)接下来仍然将mid所指元素与key进行比较，比较相等，查找成功，返回mid的值9。
假设要查找的关键字key为29，那么上述的查找还要继继续下去。由于当前mid所指的元素是28，小于29，因此下面的查找工作仍然只需在[mid+1,high]中进行。将指针iow指向mid+1的位置，并调整指针mid的位置。这时指针mid,low与high三者重合，都指向关键字32，它们的值都为10。
　（1，3，5，7，9，11，13，17，21，28，32）
　　　　　　　　　　　　　　　 　　　　　↑
　　　　　　　　　　　　　　　　　　　　high
　　　　　　　　　　　　　　　　　　　　mid
　　　　　　　　　　　　　　　　　　　　low
再将mid所指的元素与key进行比较，因为key=29,小于32，说明待查找的关键字一定位于low和mid之间。所以下面的查找工作仍然只需在[low,mid-1]中进行。于是令指针high指向mid-1的位置，即high=9，也就是指向关键字28.这是指针high小于指针low，这表明本次查找失败。
折半查找的算法如下：

int search(keytype key[],int n,keytype k){ int low=0,high=n-1,mid; while(low<=high) { mid=(low+high)/2; if(key[mid]==k) return mid;//查找成功，返回mid if(k>key[mid]) low=mid+1;//在后半序列中查找 else high=mid-1;//在前半序列中查找 } return -1;//查找失败，返回-1 }

在算法中，n表示记录的个数。key表示要查找的关键字。key[]为关键字顺序表，每个元素都是对应记录的关键字。例如key[0]为第0个记录的关键字。如果每条记录的信息与它的关键字都存放在一个记录里，如下定义：

typedef struct{ keytype key;//keytype类型的关键字key datatype data;　　//记录中的其他信息 }RecordType;

每个记录中包含一个关键字key和一个数据域data。这种记录的折半查找法可描述为：

int search(RecordType r[],int n,keytype k){ int low=0,high=n-1,mid; while(low<=high) { mid=(low+high)/2;//设置mid指针的值 if(r[mid].key==k) return mid;//查找成功，返回mid if(k>r[mid].key) low=mid+1;//在后半序列中查找 else high=mid-1;//在前半序列中查找 } return -1;//查找失败，返回-1 }

这里要注意，以上算法只适用于关键字顺序递增的有序表查找。如果该顺序表是关键字递减的，则算法需要改动，在low指针与high指针的修改上对调即可。
折半查找法的优点：折半查找法的效率比顺序查找法的效率要高很多。如果一个顺序表中有1000个关键字，应用顺序查找法查找指定的关键字，平均要比较500次。而应用折半查找法，平均只用比较9次。因此对于顺序文件记录的查找，应当使用折半查找法。
折半查找法的缺点：只能应用于关键字有序的顺序表的查找，且一般不适用于对链表中记录的查找。
折半查找法的优化：在使用折半查找前，将关键字key与上下界low与High先进行比较，若与其中一个相匹配可直接跳出，无需继续折半。
【实例】
有一个数组A[10],里面存放了10个整数，顺序递增。任意输入一个数字n，找到n在数组中的位置。如果n不属于该数组A，显示错误提示。
　　　　　　　　A[10]={2,3,5,7,9,11,12,15,19,22}
【分析】

#include<stdio.h>int search(int A[],int n,int key){ int low=0,high=n-1,mid; if(A[low]==key) return low; else if(A[high]==key) return high; else { while(low<=high) { mid=(low+high)/2; if(A[mid]==key) return mid;//查找成功，返回mid if(key>A[mid]) low=mid+1;//在后半序列中查找 else high=mid-1;//在前半序列中查找 } } return -1;//查找失败，返回-1 }main(){ int A[10]={2,3,5,7,9,11,12,15,19,22},i,n,addr; printf(“A[10]:”); for(i=0;i<10;i++) printf(“%d “,A[i]);//显示数组A的内容 printf(“\n输入要查找元素：”); scanf(“%d”,&n);//输入待查找元素 addr=search(A,10,n);//折半查找返回该元素在数组中的下标 if(addr!=-1)//查找成功 printf(“%d是数组中的第%d个元素”,n,addr+1); else//查找失败 printf(“A数组中无%d”,n); return 0;}

运行结果如图所示：

注意：数组的下标从0开始，故要在原返回值上+1，才为元素的位置。