3.9　二分查找

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好，占用系统内存较少；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

1．二分查找思想

二分查找算法的基本思想：假设序列中的元素是按从小到大的顺序排列的，以序列的中间位置为界将序列一分为二，再将序列中间位置的元素与目标数据比较。如果目标数据等于中间位置的元素，则查找成功，结束查找过程；如果目标数据大于中间位置的元素，则在序列的后半部分继续查找；如果目标数据小于中间位置的元素，则在序列中的前半部分继续查找。当序列不能被定位时，则查找失败，并结束查找过程。

中间位置的计算公式如下：

中间位置≈（结束位置－起始位置）÷2+起始位置

注意： 对计算结果进行向下取整。

2．算法分析

根据二分查找算法的基本思想，结合图3-12将该算法的工作过程描述如下。

第一次查找：起始位置为0，结束位置为7，中间位置为（7-0）/2+0≈3，序列中索引位置为3的元素是7。目标值17大于7，则继续查找元素7右侧的数据。

第二次查找：起始位置为4，结束位置为7，中间位置为（7-4）/2+4≈5，序列中索引位置为5的元素是13。目标值17大于13，则继续查找元素13右侧的数据。

第三次查找：起始位置为6，结束位置为7，中间位置为（7-6）/2+6≈6，序列中索引位置为6的元素是17。正好与目标值17相等，则将目标位置6返回，整个查找过程结束。

通过分析上述查找过程，将二分查找算法的编程思路描述如下：

（1）根据待查找序列的起始位置和结束位置计算出一个中间位置。

（2）如果目标数据等于中间位置的元素，则查找成功，返回中间位置。

（3）如果目标数据小于中间位置的元素，则在序列的前半部分继续查找。

（4）如果目标数据大于中间位置的元素，则在序列的后半部分继续查找。

（5）重复进行以上步骤，直到待查找序列的起始位置大于结束位置，即待查找序列不可定位时，则查找失败。

【例3-11】 利用二分查找法查找序列[2，3，5，7，11，13，17，19]中值为17的位置。

运行程序，输出如下： aUZg1eZsDQThvoduxFOwh5XQrGrGmuTpTNBeZvMEsymJVa8kssszXQlymwsdQTzg

     元素在数组中的索引为6