二分查( Binary Search)将待查的k值和有序表 的中间位置md=n/2上的结点的关键字进行比较,若 相等则查找成功;若k<Rmd]key则以同样的方法 在区间[0,md-1内进行查找;着k>Rrmi]key则按 同样的方法在区间rmid+1,n-1]内进行查找。又称为 折查找 012345678910 0513192137566475808892(21) low high 0513192137(21) 2137(21)
二分查找（Binary Search):将待查的k值和有序表 的中间位置mid=n/2上的结点的关键字进行比较，若 相等则查找成功；若k<R[mid].key,则以同样的方法 在区间[0，mid-1]内进行查找;若k>R[mid].key,则按 同样的方法在区间[mid+1, n-1]内进行查找。又称为 折半查找。 low mid high 05 13 19 21 37 (21) 21 37 (21) 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 75 80 88 92 （21）
23456789 0 0513192137566475808892(90) low mid low int Bin Search( seqlist r,int n, KeyType (int low=0, high=n-1,mid; while (low<=high R1190 i mid=(low+high)/2; if(rmid key==k) return mid if(rmid]. key>k) high=mid-1; ese low=mid+1 return-1
05 13 19 21 37 56 64 75 80 88 92 （90） mid 0 1 2 3 4 5 6 7 8 9 10 int BinSearch(SeqList R,int n,KeyType k) {int low=0,high=n-1,mid; while (low<=high) { mid=(low+high)/2; if (R[mid].key==k) return mid; if (R[mid].key>k) high=mid-1; else low=mid+1; } return -1; } low low mid high lowmid low high mid R 11 90
二分查找的判定比较二分查找过程可用二 叉树来描述,我们把当前查找区间的中间位置上的记 录作为根左子表和右子表中的记录分别作为根的左 子树和右子树。 0513192137566475808892(90) 回 8-9 外部结点 13 R|0.10的二分查线的判定树(n=11)
13 二分查找的判定树或比较树:二分查找过程可用二 叉树来描述,我们把当前查找区间的中间位置上的记 录作为根,左子表和右子表中的记录分别作为根的左 子树和右子树。 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 75 80 88 92 （90） 5 2 8 0 3 6 9 -1 1 2-3 4 5-6 7 8-9 10 0-1 1-2 3-4 4-5 6-7 7-8 9-10 10- 外部结点 R[0..10]的二分查线的判定树(n=11)
假设有序表的长度n=2h-1,则描述折半查找 的判定树是深度为h的满二叉树,在等概率情 况下查找成功时的平均查找长度为: ASL 4=∑PC=∑/2(n+(m+)-1 层次:1结点数:1 3 663666868 当n很大时,ASLb≈log2(n+1)-1 14
14 假设有序表的长度n=2h -1，则描述折半查找 的判定树是深度为h的满二叉树，在等概率情 况下查找成功时的平均查找长度为: log ( 1) 1 ( 1) 2 1 2 1 1 1 + − + = = = = − = n n n j n ASL PC h j j n i b s i i 当n很大时，ASLbs≈log2 (n+1)-1 层次：1 结点数：1 2 2 3 4 4 8
例10.1对于给定11个数据元素的有序表 {2,3,10,15,20,25,28,29,30,35,40},采用二分查找试 (1)若查找给定值为20的元素将依次与表中哪 些元素比较? (2)若查找给定值为26的元素将依次与哪些元 素比较? (3)假设查找表中每个元素的概率相同,求查找 成功时的平均查找长度和查找不成功时的平均查 找长度。 15
15 例 10.1 对 于 给 定 11 个 数 据 元 素 的 有 序 表 {2,3,10,15,20,25,28,29,30,35,40},采用二分查找,试 问： (1)若查找给定值为20的元素,将依次与表中哪 些元素比较？ (2)若查找给定值为26的元素,将依次与哪些元 素比较？ (3)假设查找表中每个元素的概率相同,求查找 成功时的平均查找长度和查找不成功时的平均查 找长度