以有序表表示静态查找表时，可用折半查找。
折半查找思想：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
算法
int BinarySearch(SqList L,KeyType K){
int low=1,high=L.lenght;
while(low<=high){
int mid=(low+high)/2;
if EQ(L.r[mid].key,K) return mid;
else if LT(L.[mid].key,K) high=mid-1;
else low=mid +1;
}
return 0;
}
性能分析
折半查找的过程可用一棵二叉树来表示，称为判定树，查找某个记录过程即为从根节点到该记录的所走的路径，和给定值比较的个数即为该记录所在的层数。
所以折半查找在查找成功时比较的个数不超过判定树的深度由于具有n个结点的判定树深度为（log2n）+1所以查找不成功比较的关键字也不超过（log2n）+1。
平均查找长度为ASL=[log2(n+1)]-1
扩展
斐波那契查找
平均性能比折半查找好，但最坏情况下比折半查找差
int FibonacciSearch(SqList L,KeyType K){
int Fib[]=make_fib(L,L.length);
int low=1,high=L.lenght,loc=Fib.length-1;
while(low<=high){
int mid=low+Fib[loc]-1;
if EQ(L.r[loc].key,K) return mid;
else if LT(L.[loc].key,K) {loc-=1;high=mid-1}
else{ loc-=2;low=mid+1}
}
return 0;
}
插值查找
适用于关键字分布均匀的表
int BinarySearch(SqList L,KeyType K){
int low=1,high=L.lenght;
while(low<=high){
int mid=[(K-L.r[low].key)/(L.r[high].key-L.r[low].key)]*(high-low+1);
if EQ(L.r[mid].key,K) return mid;
else if LT(L.[mid].key,K) high=mid-1;
else low=mid +1;
}
return 0;
}
