《我的折半查找法ppt课件.ppt》由会员分享，可在线阅读，更多相关《我的折半查找法ppt课件.ppt（6页珍藏版）》请在三一办公上搜索。
1、折半查找法,郑静雅,二分查找法,一、算法思想 在有序表中，取中间记录作为比较对象。 若给定值与中间记录的关键码相等，则查找成功 若给定值小于中间记录的关键码，则在中间记录的前半区继续查找；若给定值大于中间记录的关键码，则在中间记录的后半区继续查找。 不断重复上述过程，直到查找成功(条件为给定值与中间记录的关键码相等），或所查找的区域无记录，查找失败（查找数据不在数组中，条件为给定值超出初始区间或者起始位置的值大于最末位置） （最多比较log2N+1次，其中N为数组长度）,二、动态演示（以值为21的查找记录为例）,0 1 2 3 4 5 6 7 8 9,1 3 5 7 9 11 15 18 21
2、 30,21=21,219,2118,在本例中：一共比较了三次，每次都可以把查找范围缩小一半。如果查找30，则前面两次比较21换为30，第三次3021，bott=top=mid=9得到30=30找到位置a9=30。则此时比较次数最多，最多次数为四。,如果查找29,则前面比较把21改为29即可，但是第三次比较时2921，说明在比较区间的后半部分。所以bott=mid+1=9,mid=9,a9=3029.top=mid-1=8bott=9，循环结束，说明不在数组中。,查找成功a8=21,三、代码特别注意循环起始与结束条件、查找成功的条件、区间始末位置的移动、,优点是比较次数少，查找速度快，平均性能好其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。,谢谢！,
