二分法查找简介
输入:一个"有序"元素列表
输出:返回要查找的元素位置,没有这个元素则返回None
使用背景简介
假如有一个需求,在1-100顺序排列的数中找到指定的数字N,我们能想到的办法有:
方法(1), 在1开始, 挨个询问是不是1,是不是2,..., 一直到指定的N,如果N是100的话,我们需要试验到第100次才能猜中,也就是说在顺序查找中,我们最多需要100次完成需求,假设试验一次需要0.001秒,试验100次找到指定数字,最多需要0.1秒. 俗话讲: 抛开数据规模和复杂度谈算法,纯属耍流氓! 如果我们面对的是10亿个数字, 在里面查找指定数字,最多需要10亿*0.001秒 = 100万秒≈277小时
方法(2), 面对1-100, 首先最大化的排除无用数据, 先猜是不是50, 是就返回, 不是返回50是大了还是小了, 然后把50当做上边界或者下边界, 再次猜中间位置, 这样依次猜下去, 例如我们N=100,s1猜50小了, s2猜75, s3猜88, s4猜94, s5猜97, s6猜99, s7猜100共计7步找到结果, 如果是10亿需要多少次呢? 答案是()=30次
代码实现
代码截图
网友评论