二、有序查找表 上述顺序查找表的查找算法简单, 但平均查找长度较大,特别不适用 于表长较大的查找表。 若以有序表表示静态查找表,则 查找过程可以基于“折半”进行
上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用 于表长较大的查找表。 二、有序查找表 若以有序表表示静态查找表，则 查找过程可以基于“折半”进行
例如:kev=64的查找过程如下 STength STele 0513192137566475808892 01234567891011 low high low指示查找区间的下界 high指示查找区间的上界 mid=(low+high)/2
05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elem ST.length 例如: key=64 的查找过程如下： low high mid low mid high mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2
int Search Bin( SSTable st, KeyType key i low=1;high= STlength;∥置区间初值 while (low <=high)& mid=(low high)/2 if(EQ(key, STelem[mid ].key)) return mid;∥找到待查元素 else if (lt (key, STelem[mid] key)) high=mid-1;∥继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找 return O ∥顺序表中不存在待查元素 }∥ Search bin
int Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while (low <= high) { mid = (low + high) / 2; if （EQ (key , ST.elem[mid].key) ) return mid; // 找到待查元素 else if ( LT (key , ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin
分析折半查找的平均查找长度 先看一个具体的情况,假设:n=11 1 2345 6 7891011 Ci34234134234 判定树 62 9 10
先看一个具体的情况，假设：n=11 分析折半查找的平均查找长度 6 3 9 1 4 2 5 7 8 10 11 判定树 i 1 2 3 4 5 6 7 8 9 10 11 Ci 3 4 2 3 4 1 3 4 2 3 4
般情况下,表长为n的折半查找 的判定树的深度和含有n个结点的完全 二叉树的深度相同。 假设n=2h-1并且查找概率相等 ALL==>C /×2Hnxm2(m+ ∑ l)-1 i=1 在n>50时,可得近似结果 ASh≈log2(n+1)
假设 n=2h -1 并且查找概率相等 则 在n>50时，可得近似结果 一般情况下，表长为 n 的折半查找 的判定树的深度和含有 n 个结点的完全 二叉树的深度相同。 log ( 1) 1 1 2 1 1 2 1 1 1 + − + = = = = − = n n n j n C n ASL h j j n i b s i ASLbs log2 (n +1) −1