二分查找

仅当列表是有序的时候，⼆分查找才管⽤。例如电话簿中的名字是按字母顺序排序的。

如果名字不是按顺序排列的，结果将

⼆分查找。使⽤它可节省多少时间呢？

简单查找逐个地检查数字，如果列表包含100个
数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换⾔之，最多需要猜测
的次数与列表长度相同，这被称为线性时间（linear time）。
⼆分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32
次。厉害吧？⼆分查找的运⾏时间为对数时间（或log时间）。