首页 > 其他分享 >C语言实现二分法

C语言实现二分法

时间:2024-01-31 16:02:02浏览次数:20  
标签:arr 数字 实现 元素 C语言 二分法 int 搜索 数组

现在有一个任务:从一堆有序数字中找出其中一个数字

有两种方法

1)从头到尾依次寻找

2)从该些数字中中间部位比较若小于要找数字则在后半部分否则在前半部分

再进行这样的方式进行循环,直至找到或找不到此数字

现介绍这样的方法——二分法

在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半 。

现在剖析算法

首先定义一个包含n个数字的数组A中有A0<=A1<=A2.......<=An-1 在其中寻找T

(1)令L=0,R=n-1

(2)如果L>R则截止

(3)m=(L+R)/2

(4)Am<T 则L=m+1 并返回(2)

(5)Am>T 则R=m-1 并返回(2)

(6)Am=T时搜索结束,返回m


从分析可以看出可以用循环,也可以用递归

此次用循环的方法写一次

#include<stdio.h>
int main()
{
	int arr[]={0,1,2,3,4,5,6,7,8,9,12,13,22,55,66,77,78,79,80,87,88,89,90,99,100};
  int left=0;
  int sz=sizeof(arr)/sizeof(arr[0]);
  int right=sz-1;
  int k=0;
  scanf("%d",&k);
  while(left<=right)
  {
  	int mid=(left+right)/2;
    if(arr[mid]>k)
    {
    	right=mid-1;
    }
    else if(arr[mid]<k)
    {
    	left=mid+1;
    }
    else
    {
    	printf("找到了,下标为:%d\n",mid);
      break;
    }
  }
  if(left>right)
  {
  	printf("找不到");
  }
  return 0;
}







标签:arr,数字,实现,元素,C语言,二分法,int,搜索,数组
From: https://blog.51cto.com/u_16298371/9511748

相关文章

  • python网络编程(三)实现文件下载功能
    一:目标:要实现一个客户端从服务端下载文件的功能,这个在模拟ssh远程执行命令的基础上再做修改就可以了二:分析:1、要规定客户端获取文件的格式:下载文件用get文件名,比如要下载服务端的a.txt,就写成geta.txt2、因为我目前是客户端和服务端都是在一台服务器上,我模拟的时候就把......
  • python网络编程(四)用面向对象方式实现文件上传下载
    一:背景在之前已经实现了文件的下载,现在再来完善上传功能,并且使用面向对象来封装,让代码看起来更加清楚明了。二:使用规则和运行结果下载文件,下载格式get文件名get空格后面直接接文件名称,在服务端存放的文件名上传文件,上传格式put文件路径+文件名因为是上传,上传的时......
  • Applescript成功实现imessage数据筛选,imessage蓝号检测,无痕检测手机号是否注册imess
    一、imessages数据检测的两种方式:1.人工筛选,将要验证的号码输出到文件中,以逗号分隔。再将文件中的号码粘贴到iMessage客户端的地址栏,iMessage客户端会自动逐个检验该号码是否为iMessage账号,检验速度视网速而定。红色表示不是iMessage账号,蓝色表示iMessage账号。2.编写苹果MacO......
  • 企业实现细粒度权限控制的重要性和执行策略
    在信息安全领域,细粒度权限控制是一项至关重要的实践,它确保正确的人员在合适的时间访问适当的数据资源。过渡开放的权限可能会导致敏感信息轻易落入非授权者手中,而过于严格的控制则可能妨碍了正常的业务流程。因此,如何平衡权限控制的精细化与企业高效运营之间的关系,是每一个企业必......
  • iMessage蓝号检测,苹果iMessages短信,iMessages群发,iMessages推信,完美实现总结 - 电
    一、PC电脑版苹果系统(MacOS)上实现imessages群发总结为以下几种方式:/*MacOS苹果系统,正常情况下,只能安装到苹果公司自己出品的Mac电脑,俗称白苹果,不能安装到各种组装机或者其他品牌的品牌机上,黑苹果的的原理,就是通过一些“破解补丁”工具欺骗macOS系统,让苹果系统认为你的电......
  • 如何实现图片的瀑布流展示?
    工作中用到的css需要处理❓:如何实现图片的瀑布流展示?......
  • 云邮件服务器,mail服务器,邮箱群发,全自动邮件群发,http协议群发实现解析
    /*对于部署mail服务器的VPS机器笔者建议最好使用腾讯云或阿里云,毕竟在很多时候群发被被拦截的几率能大大的降低。从而达到理想的状态。域名建议联盟绿色认证或全新无任何黑历史的域名最佳。*/ 一、Mail服务器架设1:Mail服务器使用腾讯云VPS服务器(开通以后切记先解封25端口)......
  • 青海省投资集团部署智和信通运维平台,实现外网设备集中监管
    青海省投资集团是国有控股企业,是青海省财政支柱企业,公司主要业务范围是在电力、煤炭、有色金属、矿产资源、房地产开发及金融等领域进行投资。随着其信息化建设的不断开展和业务的不断扩充,IT设施出现异常运行而造成的损失和后果就愈发严重。 项目现状随着集团公司IT规模的扩大,......
  • 最好的个人博客评论区实现方案推荐:waline
    我的博客一直没有一个好看的评论区,自己做又不会。。没错,我是个前端渣渣。调研了一下,一开始想套用一些网上的静态模板,但是改造成本还是挺大的,后来接触到了Waline,简单了解了以下,我就知道了,它就是我理想中的评论区功能实现,和我的博客匹配度MAX。一、Waline简介Waline官网:https://wa......
  • ipv6 转发 ipv4 实现 FiveM 联机
    socat公网ipv6转发内网ipv4实现FiveM联机不花一分钱研究了三天终于研究明白了,首先大家需要测试家里的宽带是否有IPv6本教程基于Linux实现,因为socat目前我没找到好用的Windows版本进入[https://www.test-ipv6.com/index.html.zh_CN]如果有如下图说明是支持的如果不......