折半查找法.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 low=1 high=13 mid=7 high=6 mid=3 high=2 mid=1 1431 1418 147 low=2 mid=2 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 low=1 high=13 mid=7 high=6 mid=3 high=4 mid=5 3122 1822 2322 low=4 mid=4 2122 low=5 lowhigh int BinSearch1(int r[ ], int n, int k) //数组r[1] ~ r[n]存放查找集合 { low=1; high=n; while (low=high) { mid=(low+high)/2; if (kr[mid]) high=mid-1; else if (kr[mid]) low=mid+1; else return mid; } return 0; } 折半查找——非递归算法 int BinSearch2(int r[ ], int low, int high, int k) //数组r[1] ~ r[n]存放查找集合 { if (lowhigh) return 0; else { mid=(low+high)/2; if (kr[mid]) return BinSearch2(r, low, mid-1, k); else if (kr[mid]) return BinSearch2(r, mid+1, high, k); else return mid; } } 折半查找——递归算法 折半查找判定树 判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。 ⑴ 当n=0时，折半查找判定树为空； ⑵ 当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。 判定树的构造方法 － 1 1－2 2－3 3－4 4－5 10－11 11－ 9－10 8－9 7－8 5－6 6－7 内部结点 外部结点 3 6 9 10 11 7 8 4 5 1 2 判定树的构造方法（例：11个结点的判定树） 具有n个结点的折半查找判定树的深度为 查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。 查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。 。 ? ? 1 log 2 + n 折半查找性能分析