- T5
二分查找:最好以顺序查找方式存储,需根据下标随机访问。 - T8
折半查找:二叉判定树一定平衡。
二叉排序树:根据输入顺序,可能为单支树,可能不平衡。 - T9 T10
折半查找时,无论是向上或是向下取整,对比后mid若不相等,需low=low+1再折半。 - T12 T13
折半查找失败:若树高位4(路径长度3/4),那么对应的失败结点查找长度也为(3/4),且结点个数为虚构的失败结点个数。 - T15
分块查找 = 索引顺序表查找
(索引/子块中采用顺序查找)ASL = (b+1)/2 + (s+1)/2 = (s2+2s+n)/2;s=根号n时,ASL最小。 - T17
(索引/子块中采用折半查找)查找效率最高,s=b=根号n,ASL=log(n+1)向上取整+log(n+1)向上取整。 - T21
折半查找判定树:向上取整—只有左节点,向下取整—只有右结点。
(折半查找只可能有向上向下其中一种取整方式)