《算法图解》学习笔记一:二分查找

假设要在电话簿中找一个名字以K打头的人,(现在谁还用电话簿!)可以从头开始翻页,直到进入以K打头的部分。但你很可能不这样做,而是从中间开始,因为你知道以K打头的名字在电话簿中间。 又假设要在字典中找一个以O打头的单词,你也将从中间附近开始。 现在假设你登录Facebook。当你这样做时,Facebook必须核实你是否有其网站的账户,因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon,Facebook可从以A打头的部分开始查找,但更合乎逻辑的做法是从中间开始查找。 这是一个查找问题,在前述所有情况下,都可使用同一种算法来解决问题,这种算法就是二分查找。 二分查找是一种算