折半查找法又称为二分查找法。
一、基本思想
假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，此时查找成功；或直到子表不存在为止，此时查找不成功。
二、时间复杂度
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2]，则找到x，算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x，如果x>a[n/2]，则只要在数组a的右半部搜索x。
时间复杂度就是求while循环的次数。
假设总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k，其中k就是循环的次数。
由于n/2^k取整后>=1，令n/2^k=1， 可得k=log2(n),（以2为底n的对数）。
所以时间复杂度可以表示为O(h)=O(log2(n))
三、C语言实现
#include<stdio.h>
int binSearch(int a[], int n, int key)
{
int low ,high, mid;
low = 0;
high = n - 1;
while(low <= high)
{
mid = (low + high) / 2; // 向下取整
if(key == a[mid])
{
return mid;
}
else if(a[mid] < key)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
int main()
{
int a[] = {0, 10, 20, 30, 40, 50, 60};
int num = 20;
int n = sizeof(a) / sizeof(a[0]);
printf("%d", binSearch(a, n, num));
return 0;
}
运行结果：
2
分析：
while循环中的 “<=” 不能写成 “<”。下面举两个例子来看看没写等号的结果。
例1
a[] = {10,20}，key = 20
low = 0, high = 1, mid = (low + high) / 2 = (0 + 1) / 2 = 0, 因为a[mid] < key，low = mid + 1 = 0 + 1 = 1，此时low == high，循环结束。返回-1，表示没有找到数据。但实际上数组a中有20这个数。
例2
a[] = {10,20, 30}，key = 30
low = 0, high = 2, mid = (low + high) / 2 = (0 + 2) / 2 = 1, 因为a[mid] < key，low = mid + 1 = 1 + 1 = 2，此时low == high，循环结束。返回-1，表示没有找到数据。但实际上数组a中有30这个数。
四、二分查找的优缺点
优点是比较次数少，查找速度快，平均性能好；
缺点是要求待查表为有序表，若无序得先排序。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
加入少儿信息学奥赛QQ群请扫左侧二维码，关注微信公众号请扫右侧二维码
QQ群和公众号.png
