我的折半查找法

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