有序序列搜索问题最快算法为二分法的一个理论证明

摘要

为了证明有序序列搜索问题最快算法为二分法,先由一个具体例子引入,得到问题描述与三条初步结论。再结合二分法定义由计算均值方法得到评价算法平均收敛速度的标准。最后由数学归纳法证明有序序列搜索问题每次迭代中迭代数的性质,进而证明解决有序序列搜索问题的所有算法中,二分法算法可以达到平均最快的收敛速度。