Question

折半查找法

Answer 1

折半查找法是效率较高的一种查找方法，假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是：

设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找。

否则，若X大于am，替换下限l=m+1，到下半段继续查找。

若X小于am，换上限h=m-1，到上半段继续查找，如此重复前面的过程直到找到或者l>h为止。

如果l>h，说明没有此数，打印找不到信息，程序结束。

该方法是查找的范围不断缩小一半，所以查找效率较高。

折半查找法优缺点

Bentley在自己的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。

问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。

折半查找法的优点是比较次数少，查找速度快，平均性能好。

其缺点是要求待查表为有序表，且插入删除困难，因此折半查找方法适用于不经常变动而查找频繁的有序列表。