从今天开始我们将陆续介绍几种常见的算法，深入浅出地带你遨游算法的世界。

算法

现在几乎人人都在谈论算法，那么到底什么是算法？我们可以把算法看做一个菜谱，你只要按照它的指令去做，就会得到相应的结果。算法就是这一系列指令的集合，它并不神秘。

线性查找与二分查找

那么下面我们就来介绍一种查找数字的算法。

假设你和小明正在玩猜数字的游戏。小明说，我随便想一个1-50之间的数，你来猜我想的数字。每次你猜的时候，我会告诉你，你猜的数字比我想的是大了还是小了。那么你会如何来猜测呢？

第一种方法，你从1开始，1个1个地猜。如果小明想的数字是50，那很不幸，你要连续猜50次。

第二种方法，你觉得1步1步的猜太慢了，我何不每隔1个去猜呢？这样的话，我最多也只需要猜50/2=25次而已。

第三种方法，可能你觉得这样还是太慢了，那我一次最多跨多少个数去猜合适呢？嗯，其实你可以一次跨越一半的数字，也就是25。

也就是说，你第一次猜的数字是50的一半，25。如果小明说比25大，那么你只需考虑25的右边部分；如果小明说比25小，同样你只用考虑25的左边部分，右边忽略。相当于一下帮你剔除了一半的数据。

那接下来呢？假如小明说比25小，我们就在25的左边部分再找出居中的数字。这个数字大约是25的一半，12或者13都可以，不妨定为12。

然后小明就会给你一个信息，他想的数字是比12大还是比12小。你就可以继续重复上面的步骤，进而猜出小明所想的那个数字。

总结一下，我们猜测的路线大概是50→25→12→6→3→1。也就是说，及时在最极端的情况下，我们也只需要6步就可以完成猜测。对比其他的方法，真是快了好多啊。

我们把第一种依次进行查找的方法叫做线性查找；而最后一种一次筛选出一半数据的方法叫做二分查找。

我们知道，这个世界上有许许多多的算法。而在实际生活或工作中，算法的速度一直是我们所看重的。因为即使一个算法非常完美，但会运行可能长达数年之久，那我们也只能放弃它而去寻找一个更快的算法去完成迭代。

那么问题就来了，如何来衡量算法之间的速度呢？很多人第一时间会想到测量算法完成所需的时间，可行是可行，但由于每台计算机的性能不同，再加上其他的条件，很可能出现同样的算法测出的时间却不相同的结果。

此时，大O表示法出现了。它测量的不是算法运行所需的时间，而是算法运行所需的步数，而且是在极端情况下完成的步数。

比如我们之前提到的线性查找，如果有n个数，那么一步一步来找的话就需要n步，用大O表示法记为O(n)。

而二分查找呢，每次可以筛出一半的数据，如果有n个数的话，那么它所需的步骤就是logn，记为O(logn)。一般当log的底数为2时，我们可以省略。

那么O(n)和O(logn)哪个更快一些呢？我们可以做个表来对比下：

可以看到，当数据量越大时，O(logn)远远小于O(n)，也就是说O(logn)所对应的算法是更快的。

好了，这就是今天的全部内容，欢迎留言讨论。