折半查找法

9.2.2折半查找（二分查找）适用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。例：查找值为14的记录的过程：0123456789101112137141821232931353842464952low=1high=13mid=7high=6mid=3high=2mid=114311418147low=2mid=214=14例：查找值为22的记录的过程：0123456789101112137141821232931353842464952low=1high=13mid=7high=6mid=3high=4mid=5312218222322low=4mid=42122low=5lowhighintBinSearch1(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{low=1;high=n;while(low=high){mid=(low+high)/2;if(kr[mid])high=mid-1;elseif(kr[mid])low=mid+1;elsereturnmid;}return0;}折半查找——非递归算法intBinSearch2(intr[],intlow,inthigh,intk)//数组r[1]~r[n]存放查找集合{if(lowhigh)return0;else{mid=(low+high)/2;if(kr[mid])returnBinSearch2(r,low,mid-1,k);elseif(kr[mid])returnBinSearch2(r,mid+1,high,k);elsereturnmid;}}折半查找——递归算法折半查找判定树判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。⑴当n=0时，折半查找判定树为空；⑵当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1]~r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1]~r[n]相对应的折半查找判定树。判定树的构造方法－11－22－33－44－510－1111－9－108－97－85－66－7内部结点外部结点3691011784512判定树的构造方法（例：11个结点的判定树）具有n个结点的折半查找判定树的深度为查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。。1log2+n折半查找性能分析