二分查找法的算法过程需要注意什么

来源：蜘蛛抓取(WebSpider) 时间：2017-01-09 19:08 标签： 二分查找法时间复杂度
二分查找算法的两种实现方式
二分查找算法的两种实现方式
　　1)递归方法实现：
　　int BSearch(elemtype a[],elemtype x,int low,int high)
　　/*在下届为low，上界为high的数组a中折半查找数据元素x*/
　　if(low&high) return -1;
　　mid=(low+high)/2;
　　if(x==a[mid])
　　if(x else return(BSearch(a,x,mid+1,high));
　　2)非递归方法实现：
　　int BSearch(elemtype a[],keytype key,int n)
　　int low,high,
　　low=0;high=n-1;
　　while(low&=high)
　　mid=(low+high)/2;
　　if(a[mid].key==key)
　　else if(a[mid].key else high=mid-1;
　　return -1;
下页更精彩：1
本文已影响人
二分查找算法的两种实现方式相关推荐
[二分查找算法的两种实现方式]网友评论
<div class="ds-thread" data-thread-key="894670" data-title="二分查找算法的两种实现方式" data-image="">二分查找算法，是一种在有序数组中查找某一特定元素的搜索算法。
注意两点：
(1)有序：查找之前元素必须是有序的，可以是数字值有序，也可以是字典序。为什么
必须有序呢？如果部分有序或循环有序可以吗？
&(2)数组：所有逻辑相邻的元素在物理存储上也是相邻的，确保可以随机存取。
&&算法思想：
&搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，
则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。
&&这里我们可以看到:&
(1)&如果查找值和中间值不相等的时候，我们可以确保可以下次的搜索范围可以缩小一
半，正是由于所有元素都是有序的这一先决条件
&(2)&我们每次查找的范围都是理应包含查找值的区间，当搜索停止时，如果仍未查找到，那么此时的搜索位置就应该是
&查找值应该处于的位置，只是该值不在数组中而已
&&算法实现及各种变形：
&1.&非降序数组A,&查找任一个值==val的元素，若找到则返回下标位置，若未找到则返回-1&
2.&非降序数组A,&查找第一个值==val的元素，若找到则返回下标位置，若未找到则返回-1&(类似：查找数组中元素最后一个小于val&
值的位置)&
3.&非降序数组A,&查找最后一个值==val的元素，若找到则返回下标位置，若未找到则返回-1&(类似：查找数组中元素第一个大于val&值
4.&非降序数组A,&查找任一值为val的元素，保证插入该元素后数组仍然有序，返回可以插入的任一位置
&5.&非降序数组A,&查找任一值为val的元素，保证插入该元素后数组仍然有序，返回可以插入的第一个位置
&6.&非降序数组A,&查找任一值为val的元素，保证插入该元素后数组仍然有序，返回可以插入的最后一个位置
&7.&非降序数组A,&查找任一个&&值==val的元素，若找到则&返回一组下标区间(该区间所有值&==val)，若未找到则返回-1&
8.&非降序字符串数组A,&查找任一个值==val的元素，若找到则返回下标位置，若未找到则返回-1(类似：未找到时返回应该插入点)&
9.&循环有序数组中查找==&val&的元素，若找到则返回下标位置，若未找到则返回-1
【二分查找要求】：
1.必须采用顺序存储结构
&2.必须按关键字大小有序排列。
&【优缺点】
折半查找法的优点是比较次数少，查找速度快，平均性能好;
其缺点是要求待查表为有序表，且插入删除比较困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
阅读(...) 评论()温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。算法步骤描述① 首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2② 用待查关键字值与中间位置的关键字值进行比较；　 若相等，则查找成功　 若大于，则在后（右）半个区域继续进行折半查找　 若小于，则在前（左）半个区域继续进行折半查找③ 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放。折半查找算法举例对给定数列（有序）{ 3,5,11,17,21,23,28,30,32,50,64,78,81,95,101}，按折半查找算法，查找关键字值为81的数据元素。折半查找的算法讨论：优点：ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。考虑：能否通过一次比较抛弃更多的部分（即经过一次比较，使查找范围缩得更小），以达到提高效率的目的。……？可以考虑把两种方法（顺序查找和折半查找）结合起来，即取顺序查找简单和折半查找高效之所长，来达到提高效率的目的？实际上这就是分块查找的算法思想。Java二分查找源码&&&
阅读(14197)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
在LOFTER的更多文章
loftPermalink:'',
id:'fks_',
blogTitle:'Java二分查找算法',
blogAbstract:'二分查找又称折半查找，它是一种效率较高的查找方法。折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:7,
publishTime:4,
permalink:'blog/static/',
commentCount:0,
mainCommentCount:0,
recommendCount:1,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'0',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}

我要回帖

更多关于 二分查找法时间复杂度 的文章

 

随机推荐