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

A Theoretical Proof of Dichotomy as the Fastest Algorithm for Sequential Search Problem

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

In order to prove that the fastest algorithm for the ordered sequence search problem is method of bisection, a specific example is introduced, and the problem description and three preliminary conclusions are obtained. Combined with the definition of dichotomy, the standard of evaluating the average convergence rate of the algorithm is obtained by calculating the mean value method. Finally, the properties of the iterated algebra in each iteration of the ordered sequence search problem are proved by mathematical induction, and it is proved that the dichotomy algorithm can achieve the fastest average convergence speed among all the algorithms for solving the ordered sequence search problem.