012345678 012345678 面013468⑩12013|4 查找 查找 OZO mi high OZ mid high 600 low mid high low mid high 查找成功 查找失败国 low mid high low mic high 查找成功的例子 查找失败的例子
查找成功的例子 查找失败的例子
算法92(p220) int search Bin( SSTable st, Key Type key)∥折半查找 i int low, high, mid low=1; high-STlength while (low high) i 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 0
int Search_Bin(SSTable ST,KeyType key) // { int low,high,mid; 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; }
从有序表构造出的二叉查找树(判定树) 查找 查找 成功(10 8 P(3102 失败 0-1212 查找成功的情形 查找不成功的情形 若设n=2h-1,则描述对分查找的二叉查找树是 高度为h的满二叉树。2h=n+1,h=log2(m+1) 第1层结点有1个,查找第1层结点要比较1次; 第2层结点有2个,查找第2层结点要比较2次;∴
查找成功的情形 查找不成功的情形
92索引顺序表的查找—分块查找 )分块有序(升序或降序) 第I块中的最大(小)值小(大)于第i+1块中的最(大)小值 2)查找 (1)先查索引表—折半查找 (2)再查顺序表—顺序查找 块间有序,块内无序 typedef struct i int key; Eletype; typedef struct i Elemtype * elem; int length 3 SSTable t define block num 3
1）分块有序（升序或降序） ——第I块中的最大（小）值小（大）于第i+1块中的最（大）小值 2）查找 （1）先查索引表——折半查找 （2）再查顺序表——顺序查找 块间有序，块内无序 typedef struct { int key;} Eletype; typedef struct { Elemtype *elem; int length; } SSTable; # define BLOCK_NUM 3
Typedef struct int Markey int next; BLKNode, IT[BLOCK Num int Search Bin( SSTable st, int key)∥折半查找 f int i,p, low, high, mid printf(" Create index table, Input Maxkey& nexn?) for(i-l; K-BLOCK NUM 1++) scanf(%d, %d', &IT[i].Maxkey, &IT[i]. next if(key>IT[BLOCK NUM]. Maxkey) return(O) low=1: high=BLOCK NUM while (low <=high i mid=(low+high)/2 if (TImid. Maxkey>=key)high=mid-1 else low-mid+1
Typedef struct { int Maxkey; int next; } BLKNode,IT[BLOCK_Num]; int Search_Bin(SSTable ST,int key) // { int i,p,low,high,mid; printf(“Create index table,Input Maxkey& nex\n”) for(i=1;i<=BLOCK_NUM;i++) scanf(“%d,%d” ,&IT[i].Maxkey,&IT[i].next) if(key>IT[BLOCK_NUM].Maxkey) return(0); low = 1; high=BLOCK_NUM; while (low < =high) { mid = (low+high)/2; if (IT[mid].Maxkey>=key)) high=mid-1; else low=mid+1; }