这不是什么大事 - 你有一个顺序列表,在你给它的链接的例子中是电话簿中的名字 - 一个找到名字的好方法是
转到电话簿的中间,您要按字母顺序查找名称,而不是页面底部的名称？是的,那么你需要查看这些页面之后的页面,或者如果之前我们需要查看此页面之前的页面(或者我们已经找到它).因此,我们将下一次迭代中要查看的页数减少一半(或将其分成两半).
在我们的下一次迭代中,我们正在查看电话簿的前半部分或电话簿的后半部分.所以,让我们说名字是在上半部分,然后我们进入这一半的中间,我们的测试再次是我们在此页面上的名称之前或之后寻找的名称.
等等
我们必须做的最多次数是多少？n是页数,所以在最糟糕的情况下,我们要查找的页面是在最后一次迭代中,在最后一次迭代中,n必须等于1(或2),所以我们必须将n切成两半得到1.这个数字是log n base 2,或者是cs人们说O(log n) - 他们只是省略了基数2部分.
也许另一种看待它的方式,你有一个你想在电话簿中找到的名字.每次你看书的中间,看看你要找的名字是在书的第一页还是后半部分.你正在寻找的名字的一半是在你保持这一半而扔掉另一半.
你知道你保存的书的一半有你想要的名字.你再次进行测试,打开你保存的书的中间部分,看看你要找的名字是在上半部分还是在上半部分,保留包含名字的书的一半然后扔掉另一半.继续这样做,直到找到名字.心连心