计算机 · 二分查找
怎样在 100 万个名字中用 20 步找到一个?
你将看到
一本电话簿里有一百万个名字,按字母顺序排列。一个一个查,可能要看一百万次。能更快吗?从正中间翻开。你要找的名字在后面,所以整个前一半都可以扔掉。还剩五十万。再翻开剩下部分的中间,又砍掉一半。再来一次。每看一次,就扔掉剩下的一半。砍半二十次,一百万就只剩一个,因为二的二十次方刚好比一百万多一点。十亿个名字呢?只要再多看十次。
计算机 · 二分查找
一本电话簿里有一百万个名字,按字母顺序排列。一个一个查,可能要看一百万次。能更快吗?从正中间翻开。你要找的名字在后面,所以整个前一半都可以扔掉。还剩五十万。再翻开剩下部分的中间,又砍掉一半。再来一次。每看一次,就扔掉剩下的一半。砍半二十次,一百万就只剩一个,因为二的二十次方刚好比一百万多一点。十亿个名字呢?只要再多看十次。