什么是简单查找呢，就是给一个数组，挨个找一遍，看看自己要找的数在不在这个数组里面，或者在这个数组的哪个位置。如果这个数组的长度为 100，那么最坏的情况，也就是刚好找到最后一个才找到那个数，需要找 100 次。最好的情况下，第一个数刚好就是我们要找的，这时只需找 1 次。但是在正常情况下，我们的运气不可能总那么好，也不会总那么坏，所以就需要一个指标来衡量这种查找的效率是怎样的。
一般来说，在算法中，我们使用 大O 来表示某种算法的速度，准确的说是一种增速，就是随着数据越来越多的情况下，所需要的时间是怎样变化的。
像这种简单查找，用 大 O 表示法就可以写成 O(n) 。
那么二分查找又是什么呢，还是一个数组，但是这个数组是有序的，比如数字是按照从小到大的顺序排列的，现在从这个数组里面找一个数。
如何最快的找到这个数呢？首先，之前有说过，这个数组是有序的而且由小到大排列，那么如果第一次找到的数比要找的那个数小，就会从这个数的后面开始找，否则就从这个数的前面开始找，这样找到的第二个数再使用这个方法开始找，直至找到的数刚好和要找的这个数相等。
好，查找的方法了解了，怎么找才能使查找的次数最少呢？这里介绍一个我们经常看到的或者自己玩过的一个游戏，就是报数人在某个范围内随便报一个数，但是这个数字不能让猜数人知道，然后猜数人开始猜数，报数人每次都需要根猜数人提供的数字和自己报的数字进行比较，告诉猜数人他的数字是大了还是小了，猜数人需要在最少的回合内猜到这个数。比如现在这个数是在 1 到 100 之间，那么首先肯定就会猜 50，为什么是 50 呢，因为 50 刚好是个中间数，无论这个数字比要猜的数字大还是小，都可以排除一半范围的数。这样如果猜数人说“大了”，那就从 1 到 50 的中间数再猜，依次下去。所以，二分查找也是这样，因为数组是有序的，先找到中间值，然后根据中间值的比较结果再找中间值，直至找到的这个数。
上面说简单查找的 大 O 表示法，也就是运行时间可以表示为 O(n)，二分查找使用大 O 表示法又怎么表示呢？
还是刚才的例子，从 1 到 100 猜数，如果挨个去猜，也就是使用简单查找的话， 最差的情况是猜 100 次，但是使用二分查找的方法，每次取中间数比较，每次都能排除一半，直到最后剩下一个数，这样最差的情况是猜 7 次。而这种每次排除一半的方式，就是把数组的长度不断除以 2，直到最后的长度小于 1 。这样，二分查找的大 O 表示法就是 O(log n)。
从算法运行时间可以看出，当 n 越大，二分查找比简单查找要快的多。
网友评论