折半查找前提条件.PPT

折半查找 折半查找前提条件 折半查找也被称为是二分查找，这是一种查找效率较高的查找方法。 但是折半查找有两个前提条件： 一是线性表必须采用顺序存储结构； 二是表中元素按关键字有序排列。 算法思想 (1)将给定值key与中间位置记录的关键字进行比较，若相等则查找成功。 (2)若不相等则利用中间位置记录将表对分成前、后两个子表。如果key比中间位置记录的关键字小，则下一次只在前一子表中继续查找，否则在后一子表中继续查找。 (3)重复（1）和（2），将查找区间不断对分，知道查找成功，或者当前的查找区间为空，则查找失败。 算法描述 int Search_Bin ( SSTable ST, KeyType key ) { //在有序表ST中折半查找其关键字等于key的数据元素 //若找到，则函数值为该元素在表中的位置，否则为0 low = 1; high = ST.length; // 置区间初值 while (low = high) { mid = (low + high) / 2; if （key == ST.R[mid].key ) return mid; // 找到待查元素 else if ( key ST.R[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找} return 0; // 顺序表中不存在待查元素 } // Search_Bin ST.elem ST.length low high mid low mid high mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2 05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 例题：折半查找key=64 用二叉树描述折半查找 56 19 80 5 21 13 37 64 75 88 92 判定树 把当前查找区间的中间位置作为根，左子表和右子表分别作为根的左子树和右子树，由此得到的二叉树我们称之为折半查找的判定树。 从判定树上可见，成功的折半查找恰好是走了一条从判定树的根到被查结点的路径，所比较的次数恰为该结点在树中的层次数。 假设每个记录的查找概率相同，根据判定树，我们可以确定，长度为11的有序表进行折半查找的平均查找长度为： ASL=(1+2*2+3*4+4*4)/11=3 折半查找法在查找成功时进行比较的关键字的个数最多不超过树的深度。 另外，判定树虽然不是完全二叉树，但是其深度显然和拥有同样结点数的完全二叉树是一样的。所以，对于长度为n的有序表，折半查找法在查找成功时和给定值进行比较的次数之多为|log2n|+1。 我们可以在判定树中所有结点的空指针域上加一个指向方形结点的指针。 6 3 9 1 4 2 5 7 8 10 11 折半查找在查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的关键字个数等于该路径上内部结点个数。 因此，折半查找在查找不成功时和给定值进行比较的关键字个数最多也不超过|log2n|+1。 可见，折半查找算法的时间复杂度为O(log2n)。