11.7　二分查找

二分查找也称折半查找，其优点是查找速度快，缺点是要求所要查找的数据必须是有序序列。该算法的基本思想是将所要查找的序列的中间位置的数据与所要查找的元素进行比较，如果相等，则表示查找成功，否则将以该位置为基准将所要查找的序列分为左右两部分。接下来根据所要查找序列的升降序规律及中间元素与所查找元素的大小关系，来选择所要查找元素可能存在的那部分序列，对其采用同样的方法进行查找，直至能够确定所要查找的元素是否存在，具体的使用方法可通过下面的代码具体了解。

include＜stdio.h＞

binarySearch（int a[]，int n,int key）

{

int low=0；

int high=n-1；

while（low＜=high）

{

int mid=（low+high）/2；

int midVal=a[mid]；

if（midVal＜key）

low=mid+1；

else if（midVal＞key）

high=mid-1；

else

return mid；

}

return-1；

}

int main（）

{

int i,val,ret；

int a[8]={-32，12，16，24，36，45，59，98}；

for（i=0；i＜8；i++）

printf（"%d\t"，a[i]）；

printf（"\n请输入所要查找的元素："）；

scanf（"%d"，＆val）；

ret=binarySearch（a，8，val）；

if（-1==ret）

printf（"查找失败\n"）；

else

printf（"查找成功\n"）；

return 0；

}

运行结果：

-32 12 16 24 36 45 59 98

请输入所要查找的元素：12

查找成功

在上面的代码中，我们成功地通过二分查找算法实现了查找功能，其实现过程如图11-10所示。

图　11-10　二分查找算法的查找过程

在如图11-10所示的查找过程中，先将序列中间位置的元素与所要查找的元素进行比较，发现要查找的元素位于该位置的左部分序列中。接下来将mid的左边一个元素作为high，继续进行二分查找，这时mid所对应的中间元素刚好是所要查找的元素，查找结束，返回查找元素所对应的下标。在main函数中通过返回值来判断查找是否成功，如果查找成功，就打印输出“查找成功”的信息，否则输出“查找失败”的信息。