关于二分法查找算法的历史研究

【摘要】 本文讨论了包括J.J.Donovan在内的26名作者在设计二分法查找算法时的某些历史情况。指出了这些算法的某些错误推导。文中分析了四种典型的正确算法,即(1)关于T项单调递增序列的单纯的二分法查找算法,其中T=2~n-1,n≥1;(2)关于T项单调递增序列的二分法查找算法;(3)关于T项单调递增序列的“双向检验”的二分法查找算法,其中T≥1;(4)关于T项单调递增序列的通用二分法查找算法。 文中还指出了二分法查找算法的历史教训。更多还原