C语言| 数组的折半查找
数组的折半查找
折半查找：在已经排好序的一组数据中快速查找数据。
先排序，再使用折半查找。
【折半查找的运行过程】
1 存储数组下标 low最小的下标，mid中间的下标， high最大的下标
2 key存放查找的值，每一次对比后，都需要更新mid，而mid = (low+high)/2
3 把key和a[mid]进行对比，key>a[mid]，往右边找
low = mid+1, 更新mid=(low+high)/2，high不变
4 再把key和新的a[mid]比较，key<a[mid],往左边找
high = mid-1,更新mid=(low+high)/2,low不变
5 找到了数字，结束程序
6 当low == high，而a[mid]也不是要找的数字，说明不存在，结束程序。
【查找数字256】
1 定义一个变量key，存放要查找的数字256
2 定义变量low存储数组最小下标 mid中间下标 high最大下标
low = 0, mid = (low+high) / 2, high = 7;
3 此时a[2]=87,而key > a[2]=87,说明256在87的右边，则往右边查找
low = mid+1 = 3; 更新mid, mid=(low+high)/2=5;
4 此时a[5]=365,而key<365,说明256在365的左边，继续往左边查找
high = mid-1 = 4, mid=(low+high)/2=3,low=3;
5 此时a[3]=96,而key>96,说明256在96的右边，则往右边查找
low = mid+1 = 4, mid =(low+high)/2=4, high=4;
6 此时a[4]=256，找到了这个数字，结束程序。
【查找数字87】
1 key= 87, low=0, high=7, mid =(low+high)/2=3;
2 此时a[3]=96,而key<96,说明87在96左边，则往左边查找
high = mid-1 = 2, 更新mid =(low+high)/2=1
3 此时a[1]=54,而key>54,说明87在54的右边，则往右边查找
low = mid+1 =2, 更新mid =(low+high)/2=2
4 此时a[2]=87=key,找到了这个数字，结束程序。
【查找的数字不在数组中，查找111】
1 key=123, low=0, high=7, mid=(low+high)/2=3
2 此时a[3]=96,而key>96, 说明111在96的右边，则往右边查找
low = mid+1=4, 更新mid=(low+high)/2=5;
3 此时a[5]=365,而key<365，说明111在365的左边，则往左边查找
high = mid-1=4, mid=(low+high)/2=4
4 此时low == high, 而a[4]=256,不是我们需要查找的数，说明不存在。
【运行结果】
【程序代码】
#include <stdio.h>
int main(void)
{
int a[] = {13, 54, 87, 96, 256, 365, 666, 888};
int key; //存放要查找的数字
int low = 0; // 存储数组的最小下标
int high = sizeof(a)/sizeof(a[0]) -1; // 数组的最大下标
int mid; //指向中间元素
int flag = 0; //标志位，用于判断是否存在要找的数
printf("请输入您想查找的数：");
scanf("%d", &key);
while((low <= high))
{
//每比较一次，都需要更新mid，所以放在while循环里
mid = (low+high) / 2;
if(key < a[mid])
{
high = mid-1; //往左边找
}
else if(a[mid] < key)
{
low = mid + 1; //往右边找
}
else
{
printf("下标 = %d\n", mid); //找到数字
flag = 1; //说明数组中存在查找的数字
break; //跳出循环
}
}
//循环结束后也没找到数，说明不存在
if(flag == 0)
{
printf("Sorry, data is not found.\n");
}
return 0;
}