Innodb-------Binary Search算法

1. 背景

    * Binary Search(二分查找法)也称为折半查找法，用来查找一组有序记录数组中某一项记录。

    * 其基本思想是：将记录按有序化(递增或递减)排列

    * 查找过程中用跳跃式方式查找。

2. 优点

    * 比较次数少

    * 查找速度快

    * 平均性能好

    * 占用系统内存较少

3. 缺点

    * 数据源必须有序(递增或递减)

    * 插入删除困难

4. 例子

    例如对于[5、10、19、21、31、37、42、48、50、52]这十个数，从中查找48这条记录，如图

    从图中可以看出，3次就找到了48这个数。

    如果是顺序查找，则需要8次。

    因此二分查找法的效率比顺序查找法要好(平均来说)。

    顺序查找平均次数为：(1+2+3+4+5+6+7+8+9+10)/10=5.5次

    二分查找平均次数为：(4+3+2+4+3+1+4+3+2+3)/10 = 2.9次

      本文转自asd1123509133 51CTO博客，原文链接：http://blog.51cto.com/lisea/1978038，如需转载请自行联系原作者