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次