回顾查找问题(参见联系2.1-3),注意到如果序列A已排好序,就可以将该序列的中点与v进行比较.
根据比较的结果,原序列中就有一半可以不用再做进一步的考虑了.
二分查找算法会重复这个过程,每次都将序列剩余的部分规模减半
为二分查找写出迭代或递归的伪代码
证明: 二分查找最坏情况运行时间为θ(lgn)
附:考虑以下查找问题:
查找的过程是靠length/2来算的 最坏的情况是 按照输入的一组數的长度不断减半 直到只剩下1个数
在该情况下 计算的步骤数为 以2为底的输入数字数量的对数
所以最坏情况运行时间为θ(lgn)