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

二分法查找  时间: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次。

VirMach(8元/月)KVM VPS,北美、欧洲

VirMach,成立于2014年的美国IDC商家,知名的低价便宜VPS销售商,支持支付宝、微信、PayPal等方式付款购买,主打美国、欧洲暑假中心产品,拥有包括洛杉矶、西雅图、圣何塞、凤凰城在内的11个数据中心可以选择,可以自由搭配1Gbps、2Gbps、10Gbps带宽端口,有Voxility DDoS高防IP可以选择(500Gbps以上的防御能力),并且支持在控制面板付费切换机房和更换IP(带...

UCloud云服务器香港临时补货,(Intel)CN2 GIA优化线路,上车绝佳时机

至今为止介绍了很多UCLOUD云服务器的促销活动,UCLOUD业者以前看不到我们的个人用户,即使有促销活动,续费也很少。现在新用户的折扣力很大,包括旧用户在内也有一部分折扣。结果,我们的用户是他们的生存动力。没有共享他们的信息的理由是比较受欢迎的香港云服务器CN2GIA线路产品缺货。这不是刚才看到邮件注意和刘先生的通知,而是补充UCLOUD香港云服务器、INTELCPU配置的服务器。如果我们需要他...

ZJI(月付480元),香港阿里云专线服务器

ZJI是成立于2011年原Wordpress圈知名主机商—维翔主机,2018年9月更名为ZJI,主要提供香港、日本、美国独立服务器(自营/数据中心直营)租用及VDS、虚拟主机空间、域名注册业务。本月商家针对香港阿里云线路独立服务器提供月付立减270-400元优惠码,优惠后香港独立服务器(阿里云专线)E3或者E5 CPU,SSD硬盘,最低每月仅480元起。阿里一型CPU:Intel E5-2630L...

二分法查找为你推荐
蓝屏代码电脑启动出现蓝屏代码hd4600ati radeon hd 4600 这显卡好不好 多少钱百度云论坛哪里需要资源网盘分流?论坛、网站介绍一个……免费qq号有免费的QQ号和密码可以用的?免费erp免费的ERP哪家好用getsockopt提示出现这个怎么办?ucosiiucosii是什么?里面的OS是指什么?在看正点原子给的stm32f407开发指南的时候看到这个,什么意思?scanf返回值何为函数的返回值,比如scanf()函数的返回值?密码设置开机密码怎么设定?diskgenius免费版DiskGenius恢复文件是免费的吗
重庆服务器租用 我的世界服务器租用 免费vps 国内vps 万网域名管理 美国主机评测 Dedicated parseerror 亚洲小于500m 789电视 泉州电信 qq对话框 web服务器安全 怎么建立邮箱 吉林铁通 厦门电信 国外在线代理服务器 双线空间 阿里云邮箱登陆地址 酸酸乳 更多