二分查找问题
《二分查找问题》由会员分享,可在线阅读,更多相关《二分查找问题(4页珍藏版)》请在装配图网上搜索。
1、二分查找问题实验问题:a) 设aO:nl是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不 在数组中时,返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜 索元素在数组中时,i和j相同,均为x在数组中的位置。b) 设有n个不同的整数排好序后存放于t0:n1中,若存在一个下标i,OWiVn, 使得ti=i,设计一个有效的算法找到这个下标。基本思想:将n个元素分成个数大致相同的两半,取an/2与x作比较。如果 x=an/2,则找到x,算法终止。如果xan/2,则只要在数组a的右半部分继续搜索x。算法流程图:s魁中I可力扫blS IT初iDJS滴 逋界测试数据及结果运行图:i *C
2、z VCGCFIyPra ject serf enchazhao 1 VDebugerf erLctialiao 1 ezethe seat of this number is : 7. i is 7- j is 7 Pi*ess any key to nnit:inua)b)5) 源代码:a)#include intfindnum(int*a,intn,intx,int&lower,int&higher) intmiddle;intright=n-1;intleft=0;while(leftamiddle) left=middle+1;else right=middle-1; lower=r
3、ight+1; higher=left+1; return-1;intmain()intlower,higher,middle; inta=2,3,4,9,17,19,25,34,37,40;middle=findnum(a,10,25,lower,higher); if(middle!=-1)printf(theseatofthisnumberis:%d,iis%d,jis%d n,middle,lower,higher);else%dn,printf(cantfindthisnumber,butthemostcloseseatis:%d lower,higher);return0;b)#include intSearchnumber(inta,intn) intleft=0;intright=n-1;while(leftright-1)intmid=(left+right)/2; if(mid=amid) returnmid+1; if(midamid) right=mid;elseleft=mid;return-1;voidmain()
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。