二分法查找顺序查找和二分查找

二分法查找  时间:2021-08-04  阅读:()

汇编二分法查找

这是32模式程序,ebx接收数组地址,ecx接收数组长度,eax存放要查找的数

如果找到返回下标(从0开始计算),找不到就返回ffffffffh(-1)

;------------------------------------------------------------------

binarySearch PROC ;Receives:EBX=OFFSET array, ECX=LENGTHOF array, EAX=searchVal ;Returns:EAX=index, eax=ffffffffh means not found ;------------------------------------------------------------------- dec ecx mov esi, 0 mov edi, 0 add edi, ecx bs_L2: mov edx, esi add edx, edi shr edx, 1 cmp eax, [ebx+edx*4] je bs_found ja bs_greater dec ecx mov edi, edx jmp bs_isFinish bs_greater: inc edx mov esi, edx bs_isFinish: cmp esi, edi jl bs_L2 mov eax, -1 jmp bs_quit bs_found: mov eax, edx bs_quit: ret binarySearch ENDP

c语言中如何在链表内使用二分法查找

对于无序的链表,还是沿着头结点顺序查找比较好。

如果要用二分法查找,则先将该链表进行排序,以下是我用冒泡法对单链表进行的排序: /*单链表排序(mark=1,降序;mark=0,升序)*/ void SortList(LNode *L,int mark) { int i,j,change=TRUE; ElemType temp; LNode *p=L->next,*q; if(p && (p->next)) //如果单链表长度<2,则不用排序 { for(j=1;j<L->data && change;j++) { change=FALSE; p=L->next; q=p->next; for(i=0;i<L->data-j;i++) { if((q->data>p->data && mark) || (q->data<p->data && (!mark))) { temp=p->data; p->data=q->data; q->data=temp; change=TRUE; } p=q; q=q->next; } } } printf("排序成功 "); } /*从链表的第curI个点处开始查找第i个结点,前提:i>curI*/ LNode *GetElem2(LNode *L,int curI,int i) { LNode *p=L; while(p=p->next) if(i==(++curI)) { return p; } return NULL; } /*对排序后的链表进行二分法查找*/ int DichotomyList(LNode *L,ElemType e) { LNode *p=L; int cur=0;//cur用来保存当前的位置结点,避免每次定位结点都从头结点开始 int left=1,right=L->data;//我定义的链表,其头结点的数据域保存着链表的长度 int mid=(left+right)/2; //SortList(L,0); while(left<=right && (p=GetElem2(p,cur,mid))->data!=e) { if(p->data>e) {cur=0;p=L;right=mid-1;mid=(left+right)/2;} else {cur=mid;left=mid+1;mid=(left+right)/2;} } if(p->data==e) {printf("find node in %d. ",mid);return mid;} else {printf("find none. ");return 0;} } 经VC上测度通过 如果你要完整的程序的话,留个邮箱,我发给你

C语言 二分法查找次数公式怎么推导?

对具有n个元素的有序数组进行二分法查找,要分析的比较次数,可以使用画二叉判定树的方法来分析。

该二叉判定树的高度为[log2(n)]+1层,此即为二分查找的最多比较次数,比如:n=1000,则最多比较[log2(1000)]+1=9+1=10次。

? ? 如果要计算平均的比较次数,则需要对二叉判定树中的每个节点进行分析,处于第一层的比较1次,第二层的比较2次,第三层比较3次,依次类推……把各个节点的比较次数累加,再处于节点数(元素个数)即为平均比较次数,这里假设查找是在等概率的情况下进行的。

? ? 举个例子:有9个元素的有序数组,对每个元素按1,2,3...8,9进行编号,则其二叉判定树如下: 图中可以看出,如果要找的元素处在第5个位置,则只要1次比较即可找到,若找第9个元素,则需要4次比较,算法分别比较了第5,7,8,9等4个元素。

所以,平均的比较次数大概如下: 这样分析,能看懂吗?希望能帮到你!

数据结构中,二分法查找30,怎么查找?如:7,9,14,15,17,23,30,31,45,66。请给出详细的方法!谢谢!

#include <stdio.h> int BinSearch(int a[],int k) { int l=1,h=10; //h为数组长度 while(l<=h) { int i=0; i=(l+h)/2; //找到中间位置 if(a[i]==k) { return i; } else if(a[i]>k) //在左子表查找 { h=i-1; } else{ //在右子表查找 l=i+1; } } return -1; //没找到 } int main() { int t=0; int A[10]={7,9,14,15,17,23,34,31,45,66}; t=BinSearch(A,30); printf("A[%d]=30 ",t); return 0; }

顺序查找和二分查找

答案是A。

应用顺序查找法时,查找1需要比较1次;应用二分查找法时,查找1需要比较3次,总次数为4次。

其他元素的总查找次数均超过4次。

速云:广州移动/深圳移动/广东联通/香港HKT等VDS,9折优惠,最低月付9元;深圳独立服务器1050元/首月起

速云怎么样?速云,国人商家,提供广州移动、深圳移动、广州茂名联通、香港hkt等VDS和独立服务器。现在暑期限时特惠,力度大。广州移动/深圳移动/广东联通/香港HKT等9折优惠,最低月付9元;暑期特惠,带宽、流量翻倍,深港mplc免费试用!点击进入:速云官方网站地址速云优惠码:全场9折优惠码:summer速云优惠活动:活动期间,所有地区所有配置可享受9折优惠,深圳/广州地区流量计费VDS可选择流量翻...

湖北50G防御物理服务器( 199元/月 ),国内便宜的高防服务器

4324云是成立于2012年的老牌商家,主要经营国内服务器资源,是目前国内实力很强的商家,从价格上就可以看出来商家实力,这次商家给大家带来了全网最便宜的物理服务器。只能说用叹为观止形容。官网地址 点击进入由于是活动套餐 本款产品需要联系QQ客服 购买 QQ 800083597 QQ 2772347271CPU内存硬盘带宽IP防御价格e5 2630 12核16GBSSD 500GB​30M​1个IP...

CloudCone 新增洛杉矶优化线路 年付17.99美元且简单线路测试

CloudCone 商家在以前的篇幅中也有多次介绍到,这个商家也蛮有意思的。以前一直只有洛杉矶MC机房,而且在功能上和Linode、DO、Vultr一样可以随时删除采用按时计费模式。但是,他们没有学到人家的精华部分,要这样的小时计费,一定要机房多才有优势,否则压根没有多大用途。这不最近CloudCone商家有点小变化,有新人洛杉矶优化线路,具体是什么优化的等会我测试看看线路。内存CPU硬盘流量价格...

二分法查找为你推荐
链接转换一个VB程序,简单的链接转换,怎么做?ripperJack The Ripper是谁,也就是说凶手是谁?安全防护谈谈你对自我安全防护的看法,如何保障自身安全和企业安全?cs躲猫猫cs躲猫猫怎么联机 今天在一个视频上看到的,T可以变成地图上的一个物品CT是找,请问怎么和老外联机diskgenius免费版diskgenius免费版怎么用torrent文件怎么打开BT文件怎么打开系统登录界面电脑用户登录界面,输入密码登不进去了,怎么解决,急系统登录界面192.168.0.1登录页面蓝牙开发蓝牙技术到底是指什么?赵锡成上海交大有什么好玩的
a5域名交易 java主机 la域名 idc测评网 网站挂马检测工具 100m免费空间 元旦促销 可外链相册 免费cdn 中国电信宽带测速器 网页提速 网站加速软件 注册阿里云邮箱 rewritecond 石家庄服务器 认证机构 ftp是什么东西 screen 大硬盘分区 ddos攻击教程 更多