S>二分查找(顺序有序表)二分查找（binarySearch）：也称折半查找。int BinSearch(StaticSrhTable SST, KeyType kval){//置查找范围初值bot=l, top=SST.len;while(bot<=top){mid = (bot+top)/2:if（SST.elem[mid].key==kval）returnmid；//查找成功else {if(SST.elem[midl.key>kval)top=mid-1l;//前半区//后半区else bot =mid+l;11//未查找到return O:76中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 6 中国科学技术大学 ➢ 二分查找 (顺序有序表) 二分查找（binary Search）：也称折半查找。 int BinSearch(StaticSrhTable SST, KeyType kval){ bot=1, top=SST.len; // 置查找范围初值 while(bot<=top) { mid = (bot+top)/2; if (SST.elem[mid].key==kval) return mid; //查找成功 else { if (SST.elem[mid].key>kval) top=mid-1;//前半区 else bot =mid+1; // 后半区 } } return 0; // 未查找到 }
S丫二分查找平均查找长度（假设满二叉树）ASLbs= (n+1) /nlog(n+1)-lASLbs=(20+21*2+...+2h-1*h)Pi-= Zi * 2i-1 (n=2h-1)2 i=t+1令： S=Zi*2i-1=2hi* 2i-22 Zh-1(t + 1)2t-1=2-1 t * 2t-1+2Zh-1 2t-1=2(2h t * 2t-1 - h * 2h-1)+Zh-1 2t=2(S - h * 2h-1) + 2h - 1所以: S =h * 2h - 2h + 1 =(n + 1)log2(n+ 1) -nb==s = n+1log2(n+ 1) - 1EASLhypb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 二分查找平均查找长度（假设满二叉树） ASLbs＝（n＋1）/nlog(n+1)-1 ASLbs=(2 0+2 1*2+.+2 h-1*h)Pi=
索引（分块）查找又称索引顺序香找一介于顺序查和折半查找之间。适合于关键字分块有序typedef struct {KeyType key,intstadr,↑indexItem;typedef struct:indexItem *elem;intlength;indexTable;设索引长度b，顺序表长度为n，则：ASLidx=ASL(b)+ASL(n/b)=log2(b+1)-1+(n/b+1)/28中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 8 中国科学技术大学 • 又称索引顺序查找 – 介于顺序查和折半查找之间。适合于关键字分块有序 typedefstruct { KeyType key; int stadr; }indexItem; typedefstruct{ indexItem *elem; int length; }indexTable; 设索引长度b，顺序表长度为n，则： ASLidx=ASL(b)+ASL(n/b)≈log2 (b+1)-1+(n/b+1)/2 索引(分块)查找
stateBlklnxSearch(StaticSrhTableSST, InxTab Inx, KeyTypekval)bot=1,top=Inx.len,blFound=FALSE：//置查找范围初值Ⅱ越界if (kval > Inx.elem[top].key) return 0;while (bot <= top && !blFound)[mid = (bot + top) / 2;Ⅱ查找成功if (Inx.elem[mid].key == kval) [blFound= TRUE;bot=mid;为什么选择bot而不是top？else{if (Inx.elem[mid].key>kval) top = mid - 1; I/ 前半区Ⅱ后半区else bot = mid + 1;71l/退出循环时，bot所指的为所找的块bn=Inx.elem[bot].StartAdd；/第bot块的数据记录起始地址if (bot < Inx.len) en = Inx.elem[bot + 1].StartAdd - 1;/第bot块的数据记录尾地址else en = SsT.len;for (i = bn; (i<= en) && (SST.elem[ij.key!= kval); i++);if (i <= en) return i;Ⅱ未查找到return O;1
state BlkInxSearch(StaticSrhTable SST, InxTab Inx, KeyType kval){ bot = 1, top = Inx.len, blFound = FALSE; // 置查找范围初值 if (kval > Inx.elem[top].key) return 0; // 越界 while (bot <= top && !blFound) { mid = (bot + top) / 2; if (Inx.elem[mid].key == kval) { // 查找成功 blFound = TRUE; bot = mid; } else { if (Inx.elem[mid].key > kval) top = mid - 1; // 前半区 else bot = mid + 1; // 后半区 } } //退出循环时，bot所指的为所找的块 bn = Inx.elem[bot].StartAdd; //第bot块的数据记录起始地址 if (bot < Inx.len) en = Inx.elem[bot + 1].StartAdd – 1; else en = SST.len; //第bot块的数据记录尾地址 for (i = bn; (i <= en) && (SST.elem[i].key != kval); i++); if (i <= en) return i; return 0; //未查找到 } 为什么选择bot 而不是top?
索引顺序查找索引表1726487696块内最大关键字5811518块的起始序号SST.elem74842295232766817101682126234730408696822345678910111213141516171801192010中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学 索引顺序查找 索引表 17 26 48 76 96 1 5 8 15 18 块内最大关键字 块的起始序号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 17 10 16 8 21 26 23 47 30 40 32 48 42 29 76 52 68 86 96 82 SST.elem