为什么二分查找比较快？
高中？还是初中？数学我们就学过，对于一系列有顺序的数字，要找其中的一个数字，我们每次以中间为分割点，然后找左边，或者找右边，循环下去(二分查找)，往往比每次从第一个数字开始找快。为什么呢？我们简单的探讨一下。
我们假设有10个有序的数字：
1, 2, 3, ... 10方法一：我们使用每次从1开始找的方法：
如果我们每次都从1开始找的话，找到1需要比较1次，找到2需要比较2次，。。。找到10需要比较10次，假设1,2,3,...10出现的概率是一样。那找到每个数字的平均比较次数为(1+2+3+...+10)/10 = 5.5次
方法二：二分查找法
二分查找法的比较次数，直接文字描述比较麻烦，我们画个图(见下)这个图怎么理解呢？基于二分查找的思路，我们每次先找中间值进行比较。比如找1，有如下首先，找到中间值5，因为1 < 5那就在5的左边也就是1-4找；找到1-4的中间值为2，因为1 < 2 那就在1-2找；找到1-2的中间值为1，于是返回。别的数字类似，于是可以画出如下的比较图。我们数一下图可以知道，找到1需要比较5->2->1共3次，2需要2次。。。于是我们可以算出平均比较次数为(3+2+3+4+1+3+4+2+3+4)/10 = 2.9(应该没计算错，算错了我也不管了，哈哈哈哈哈)
显然2.9比5.5小很多，所以二分查找往往是比较快的。。。
下面的知识涉及到编程知识，不感兴趣的读者忽略。。。
对于方法一，每次找数字大约需要比较N次，故时间复杂度为O(N)。(这么说是不严谨的，仅限帮助理解)
对于方法二，找数字的时候依次比较的为N/2，N/4，N/8，故时间复杂度为O(logN)。(同样是不严谨的，仅限帮助理解)
我们知道logN显然在大部分时候是远远小于N的，比如N等于1000的话，logN仅为10。
但是，二叉查找每次都需要随机访问，(N/2, N/4, N/8...)所以对于链表等不支持随机访问的数据结构就无法实现了。
而对于有序数组的查找，二分查找往往是较为理想的选择。
THE END
今天终于不用凑字数了