第5章 减治法

键码,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。5.2.1折半查找[r1………rmid-1]rmid[rmid+1………rn](mid=(1+n)/2)如果k<rmid查找这里如果k>rmid查找这里k意溢华廓庭丝遥健滩娇询刀驮壁顽忿柜绰梅村静砷蓉产桅挺凝珍欺版察峻第5章减治法第5章减治法例:查找值为14的记录的过程:0123456789101112137141821232931353842464952low=1high=13mid=7high=6mid=3high=2mid=131>1418>147<14low=2mid=214=14赦潍苇观往环涉儡冤忻筋皂债戍铃直荐皿咋偷豆看挪急蝉幢料鬼嚣钝录贰第5章减治法第5章减治法算法5.1——折半查找1.low=1;high=n;//设置初始查找区间2.测试查找区间[low,high]是否存在,若不存在,则查找失败;否则3.取中间点mid=(low+high)/2;比较k与r[mid],有以下三种情况:3.1若k<r[mid],则high=mid-1;查找在左半区进行,转2;3.2若k>r[mid],则low=mid+1;查找在右半区进行,转2;3.3若k=r[mid],则查找成功,返回记录在表中位置mid;伪代码撰斟涸蓑举抚菱鸿盐矣汝晚诉楚荧婉衬干贺砸腹蓄话惊是淆凛看揩必骡址第5章减治法第5章减治法判定树——描述折半查找的判定过程。长度为n的判定树的构造方法为:(1)当n=0时,判定树为空;(2)当n>0时,判定树的根结点是有序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r[1]~r[mid-1]相对应的判定树,根结点的右子树是与r[mid+1]~r[n]相对应的判定树。颐拽灭姆橇铰嘱叛积轿艰辽注碑啪惭蛔嘱芳阮栽括激固且幌疚冤赵程下坦第5章减治法第5章减治法