二分查找
思想：
先确定待查记录所在范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
代码：
#include<stdio.h>
#include<stdlib.h>
#define LIST_SIZE 12
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
}SSTable;
int Init(SSTable *ST,ElemType a[LIST_SIZE]){
int i;
ST->elem = (ElemType *)malloc(LIST_SIZE * sizeof(ElemType));
if(!ST->elem)
return 0;
ST->length = LIST_SIZE;
for(i = 1;i < ST->length;i++)
{
ST->elem[i] = a[i];
}
return 1;
}
void print(SSTable ST){
int i;
printf("\n元素：");
for(i = 1;i < ST.length;i++)
{
printf("%-2d ",ST.elem[i]);
}
printf("\n下标：");
for(i = 1;i < ST.length;i++)
{
printf("%-2d ",i);
}
}
int Search_Bin(SSTable ST,ElemType key){
int low,high,mid;
low = 1;
high = ST.length;
while(low <= high){
mid = (low+high)/2;
printf("\n当前比较元素为：%d 下标：%d\n",ST.elem[mid],mid);
if(key == ST.elem[mid])
return mid;
else if(key < ST.elem[mid])
high = mid - 1;
else
low = mid + 1;
}
return 0;
}
int main(){
SSTable ST;
int index,input,a[LIST_SIZE] = {0,5,13,19,21,37,56,64,75,80,88,92};
Init(&ST,a);
while(1){
system("cls");
print(ST);
printf("\nPlease Input:");
scanf("%d",&input);
index = Search_Bin(ST,input);
if(index > 0)
printf("\n查找成功！ 下标为：%d",index);
else
printf("\n查找失败！");
printf("\n\n按任意键继续. . . ");
getch();
}
return 0;
}
运行效果：
查找成功：
查找失败：
效率：
平均查找长度：ASL = (n+1)/n*log2(n+1) - 1
当n较大时：
ASL = log2(n+1) - 1
注：折半查找仅限于线性存储结构。
