算法是一组完成任务的指令。任何代码片段都可视为算法,下面我们要讨论二分查找,并演示算法如何能够提高代码的速度。在一个示例中,算法将需要执行的步骤从40亿个减少到了32个!
从生活入手的查找假设要在电话簿中找一个名字以K打头的人,(现在谁还用电话簿!)可以从头开始翻页,直到进入以K打头的部分。但你很可能不这样做,而是从中间开始,因为你知道以K打头的名字在电话簿中间。
又假设要在字典中找一个以O打头的单词,你也将从中间附近开始。
现在假设你登录Facebook。当你这样做时,Facebook必须核实你是否有其网站的账户,因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon,Facebook可从以A打头的部分开始查找,但更合乎逻辑的做法是从中间开始查找。
这是一个查找问题,在前述所有情况下,都可使用同一种算法来解决问题,这种算法就是二分查找。
做个小游戏二分查找是一种算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回null。
下图是一个例子。
下面的示例说明了二分查找的工作原理。我随便想一个1~100的数字。