算法——二分查找

算法是什么？在这里参考一下维基的定义。

在数学和计算机科学/算学之中，算法/演算法/算则法（Algorithm）为一个计算的具体步骤，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和初始输入（可能为空）开始，经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

对于不了解的人来说，算法是一个黑盒子，输入一个东西会神奇的转变为另一个东西；而这个名为算法的盒子里装的是精密制作的转化工具，有一组完成任务的指令构成，只不过这些指令不是随意拼凑的，而是需要符合某些规则进行特意的设置，我们学习算法要学习的就是某些规则。

今天要说的是一种很基本的查找方法，二分查找，很基本，但是在很多时候也是非常好用的。

二分查找有特殊的使用场景，查找的数据是有序的（不管是数字有序还是字母，只要是有序的就行）。

打个比方，你想知道德玛西亚排位分派在第152454名的是谁？这时候你应该怎么去查找呢？

最简单的方法，直接找到，第152454名看一下是谁。

哈哈，上面扯个淡，大多数情况下我们不方便直接看数据库里面的数据，所以很多时候需要用程序查找，找到之后返回我们第152454名对应的ID，这时候我们就可以用到二分查找了。

不用二分查找可以吗？可以啊，你可以从1开始查，一直查大152454，但是这样的效率低下，数据量小无所谓，数据量大，步骤会很多。那么用二分查找怎么查呢？

我们用一个小一点数据量的例子说明一下，0--99，100个数，我们要找到98，怎么做呢？二分，顾名思义，一分为二，先拿出来50和要查找的98比较，发现下了，可以排除掉0--50了；再拿出来75和98比较，发现又下了，排除51--75；依次，最后圈定98的范围。

时间复杂度，其实就是运行时间，优秀的算法就是效率最高的算法，能够最大限度的减少运行时间或者占用空间。

回到前面的二分查找。使用它可节省多少时间呢？简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。
二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32次。厉害吧？二分查找的运行时间为对数时间（或log时间）。

在看算法的时候我们经常看到一个大写的O，后面会跟着log或者别的东西，这个O是一种表示法，用来表示算法的性能，算法有多快。简单查找的速度是O(n),二分查找是O(log n)。