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]j.key) high = mid - 1;/继续在前半区间进行查找else low=mid+ 1；//继续在后半区间进行查找return O:/顺序表中不存在待香元素//SearchBin
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=1191032584672Ci233.343444判定树63
先看一个具体的情况，假设：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并且查找概率相等n+.则ASLbs=-≥C,=-j×2-1log2 (n + 1) - 1nn i=ln=在n>50时，可得近似结果ASLbs ~ log2(n +1) -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 bs i ASLbs log2 (n +1) −1
索引顺序表的查找过程：1）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找可见，索引顺序查找，是一人“缩小区间”的查找过程。具体实现是分块查找注意：索引可以根据查找表的特点来构造
索引顺序表的查找过程： 1）由索引确定记录所在区间； 2）在顺序表的某个区间内进行查找。 注意：索引可以根据查找表的特点来构造。 可见， 索引顺序查找，是一个“缩小区间” 的查找过程。具体实现是分块查找
分块查找是顺序查找的一种改进，在表的基础上又建立一个“索引表”顺序表可分为若干子表，为每个子表建立一个索引项索引表中每个索引项包括两项内容：关键字项（其值为该子表内的最大关键字）和指针项（指示该子表的第一个记录在表中位置）>索引表按关键字有序顺序表或者有厚序或者分块有序分块有序：在相邻的两个子表中，后一个子表中所有记录的关键字均大于前一个子表中所有记录的关键字
分块查找是顺序查找的一种改进，在表的 基础上又建立一个“索引表”。 ➢ 顺序表可分为若干子表，为每个子表建立一个索引项。 索引表中每个索引项包括两项内容：关键字项（其值 为该子表内的最大关键字）和指针项（指示该子表的 第一个记录在表中位置） ➢ 索引表按关键字有序。 ➢ 顺序表或者有序或者分块有序。分块有序：在相邻的 两个子表中，后一个子表中所有记录的关键字均大于 前一个子表中所有记录的关键字