有序表的查找

有序表为各元素的key值依次排序组成的查找表
如：学号，座位号等

先确定待查记录的范围，然后逐步缩小范围(递归操作实现)，直到找到/找不到为止，每次缩小范围取中间值。
递归调用中，各部分所填参数为：

	left(real)	right(not real)	right(real)
left_part	left	mid	mid - 1
right_part	mid + 1	right	right - 1

平均查找长度：
$$
ASL=log(n + 1) - 1
$$

利用斐波那契数列的性质，以相邻两个斐波那契数为边界来确定key的范围。
一般情况下，优于折半查找，但在最坏情况下劣于折半查找。

平均查找长度：
$$
ASL=(n + 1)log(n + 1) - 1/n
$$

将长度为n的表平分数个大小相等的区域，每个区域有s个元素，且每个区域按照顺序划出范围。查找时先寻找范围，后进一步查找。
效率不及折半查找。

平均查找长度(约等)：
$$
ASL=log((n/s) + 1) + s/2
$$

一种二叉树，所有节点的左节点均小于该节点，右节点均大于该节点，形成了一种微妙的范围表示法。
该树特点在于动态查找有序表，可随查找过程准确定位添加新节点。