根据王道教材编写的折半查找的示例代码。
折半查找的题目示例：
/*
时间：2022年7月22日21:06:51
作者：Mythe
根据王道书上的代码，写的折半查找的示例代码。
*/
# include <stdio.h>
# include <stdlib.h>
typedef struct List {
int * data;
int length;
}List, *SeqList;
// 将数据初始化为从0到1000
void InitList(SeqList L)
{
L->data = (int *)malloc(sizeof(int) * 1001);
L->length = 0;
int i = 0;
for (i=0; i<1000; i++) {
L->data[L->length] = i + 1;
L->length++;
}
return;
}
int BinarySearch(SeqList L, int key)
{
int i = 0;
int low = 0, high = L->length - 1;
int middle = 0;
while (low <= high) {
middle = (low + high) / 2; // 计算middle的值为两者中心
int val = L->data[middle];
printf("第%2d次比较，low=%3d，high=%3d，middle=%3d，数值：%3d，结果：", i++, low, high, middle, L->data[middle]);
if (val < key) {
low = middle + 1; // 如果给定的值比当前中心位置大，则让low指针指向middle的下一个位置
} else if (val > key) {
high = middle - 1; // 如果给定的值比当前中心位置小，则让high指针指向middle的上一个位置
} else {
printf("成功。\n");
return middle;
}
printf("失败。\n");
}
// 当low的值大于high的值时，while循环退出，此时说明没有查找到目标的值，返回-1。
return -1;
}
int main(void)
{
int key;
SeqList L = (SeqList)malloc(sizeof(List));
printf("----- 折半查找演示程序 ------\n");
printf("顺序表存放1-1000之间的整数，请输入你要查找的数：");
InitList(L);
scanf("%d", &key);
printf("index = %d\n", BinarySearch(L, key));
return 0;
}
运行截图：
