折半查找法.ppt

9.2.2 折半查找（二分查找）,适用条件： 线性表中的记录必须按关键码有序； 必须采用顺序存储。,基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,例：查找值为14的记录的过程：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,1431,1418,147,14=14,例：查找值为22的记录的过程：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,3122,1822,2322,2122,lowhigh,int BinSearch1(int r , int n, int k) /数组r1 rn存放查找集合 low=1; high=n; while (lowrmid) low=mid+1; else return mid; return 0; ,折半查找非递归算法,int BinSearch2(int r , int low, int high, int k) /数组r1 rn存放查找集合 if (lowhigh) return 0; else mid=(low+high)/2; if (krmid) return BinSearch2(r, mid+1, high, k); else return mid; ,折半查找递归算法,折半查找判定树,判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。, 当n=0时，折半查找判定树为空； 当n0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r1 rmid-1相对应的折半查找判定树，根结点的右子树是与rmid+1 rn相对应的折半查找判定树。,判定树的构造方法,判定树的构造方法（例：11个结点的判定树）,具有n个结点的折半查找判定树的深度为,查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。,查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。,折半查找性能分析,