C++二分查找详解-程序员宅基地

一、介绍：

二分查找又称折半查找，是一种相比较顺序查找效率较高的查找方法。但是，二分查找要求线性表中的记录必须采用顺序存储。

二、比较演示：

三、方法：

（1）设置查找区间：

int left;// C++自动初始化为0
int right=n;

（2）若查找区间 $[left,right]$ 不存在，则查找失败，返回 $0$ ；否则执行（3）。

（3）取中间位 $mid=(left+right)/2$ ，比较 $x$ 与 $a[mid]$ ，有三种情况：

                1. 若 x < a[mid]，则right = mid - 1；查找在左半区间进行，转（2）；

                2. 若 x > a[mid]，则left = mid + 1；查找在右半区间进行，转（2）；

                3. 若 x = a[mid]，则查找成功，返回mid的值；

四、时间复杂度比较：

（1）顺序查找：

1.最好时间复杂度：

$O(1)$

2.最坏时间复杂度：

$O(n)$

（2）二分查找：

1.最好时间复杂度：

$O(1)$

2. 最坏时间复杂度：

$O(log_{2}n)$

五、代码部分：

#include<iostream>
using namespace std;
int n, x, a[105];
int bs(int left, int right, int x) {
	int mid = (left + right) / 2;
	if (x < a[mid]) {
		return bs(left, mid - 1, x);
	}
	else if (x > a[mid]) {
		return bs(mid + 1, right, x);
	}
	else {
		return mid;
	}
}
int main() {
	cin >> n >> x;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << bs(0, n, x);
	return 0;
}

如果这篇文章对你有帮助的话，记得点个赞和收藏再走啊！！！

本文链接：https://blog.csdn.net/FlyFree56/article/details/127159790

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Java基础进阶多线程概述_一个进程可以启动多个线程,比如:对于java程序来说-程序员宅基地

文章浏览阅读6.3k次。CPU的处理速度极快，多个线程之间频繁切换执行，跟人来的感觉是：多个事情。不能够做到真正的多线程并发，但是可以做到给人一种“多线程并发”的感觉。对于单核的CPU来说，在某一个时间点上实际上只能处理一件事情，但是由于。线程A和线程B频繁切换执行，人类会感觉音乐一直在播放，游戏一直在运行，一根钢针扎到手上，到最终感觉到疼，这个过程是需要“很长的”时间的，在。我在窗口1购票，你可以在窗口2购票，你不需要等我，我也不需要等你。人类的眼睛产生了错觉，感觉是动画的。一个是垃圾回收线程，一个是执行main方法的主线程。_一个进程可以启动多个线程,比如:对于java程序来说

谈谈软件从业学习方向_大型 erp 系统,掌握 peoplesoft、oracle finacial、j.d.edward-程序员宅基地

文章浏览阅读241次。　　一、关于企业计算方向　　　　企业计算(EnterpriseComputing)是稍时髦较好听的名词，主要是指企业信息系统,如ERP软件(企业资源规划)、CRM软件(客户关系管理)、SCM软件(供应链管理，即物流软件),银行证券软件,财务软件,电子商务/政务(包括各种网站)，数据仓库，数据挖掘，商务智能等企业信息管理系统. 　　　　企业计算领域对人才的需求显然永远是数量最大的,_大型 erp 系统,掌握 peoplesoft、oracle finacial、j.d.edward、 siebel 等大型 e

贴片电容封装及尺寸示意图-程序员宅基地

文章浏览阅读2.3k次。0603封装尺寸图英制封装图尺寸：0603公制封装图尺寸：16080805封装尺寸图A-3216封装尺寸图表面贴装元件公制封装图尺寸：A-3216钽电容耐压10VB-3528封装尺寸图表..._c0603封装尺寸对照表

基于Spring Boot实现Mybatis的多数据源切换和动态数据源加载_mybatis 动态切换数据源-程序员宅基地

文章浏览阅读2w次，点赞12次，收藏69次。Spring Boot Mybaits mybatis基本配置、多数据源切换、动态加载数据源_mybatis 动态切换数据源

StandardEngine[Catalina].StandardHost[localhost].StandardContext[]_[standardengine[catalina].standardhost[localhost].-程序员宅基地

文章浏览阅读5k次。具体问题：Caused by: java.lang.ClassCastException: org.apache.tomcat.util.scan.StandardJarScanner cannot be cast to org.apache.tomcat.JarScannerorg.apache.catalina.LifecycleException: Failed to st..._[standardengine[catalina].standardhost[localhost].standardcontext

能贴在Windows11桌面且与手机同步的备忘记事便签_win11 stickly note 手机版-程序员宅基地

文章浏览阅读2k次。Windows11系统已经有不少人在用，如果你也把Windows系统升到了win11，为了方便工作，首先要确定一下win11里自己常用办公软件是否在。如果是健忘一族，一定要给自己找一款好用的便签。一款好用的便签，不但能记事备忘，还能有效地梳理工作，提高工作效率。有人找便签，喜欢找能贴在Windows11桌面，且能与手机同步的备忘记事便签。这样的便签存在吗？如果存在的话，哪个便签比较好用呢？这样的便签当然有，能贴在桌面使用的跨平台同步便签敬业签非常好用。敬业签支持在Windows、web、Android_win11 stickly note 手机版

随便推点

9、数据采集系统Flume配置安装_修改文件，配置文件flume-env.sh-程序员宅基地

文章浏览阅读200次。Flume配置安装Flume是Cloudera提供的一个高可用的，高可靠的、分布式的海量日志采集、聚合和传输的系统，Flume支持在日志系统中定制各类数据发送方，用于收集数据；同时，Flume提供对数据进行简单处理，并写到各种数据接受方（可定制）的能力。Flume特点如下：Flume可以高效率的将多个网站服务器中收集的日志信息存入HDFS/HBase中Flume可以将从多个服务器中获取的数..._修改文件，配置文件flume-env.sh

[ArcGIS笔记] 栅格图像如何显示经纬度坐标_栅格坐标-程序员宅基地

文章浏览阅读1.3w次，点赞3次，收藏31次。网上下载的栅格数据是WGS84坐标系，显示的是xy坐标，想要让它显示经纬度坐标，步骤如下：1.设置合适的坐标系。（1）了解数据的原有坐标系打开栅格数据后会发现没有空间参考信息，需要首先设置一下坐标系。注意一定要和源数据的坐标系相同。比如说本数据数采用WGS84的投影坐标系。（2）输出TIFF图像本人通过工具箱的定义投影、属性的编辑，都没有办法给栅格数据添加坐标系，于是上网查找找到了一种办法，如图：首先打开图层组的属性，设置数据框属性的坐标系为web mercator投影。然后右键图层，_栅格坐标

istio 简介-程序员宅基地

文章浏览阅读4.9k次，点赞7次，收藏30次。文章目录什么是 istio？istio 解决了什么痛点？总结istio 的解决方案流量管理安全性可观察性平台支持什么是 istio？讲多了记不住，那就：服务网格 + 微服务治理。istio 解决了什么痛点？了解Istio得从微服务架构谈起，微服务是在2012年提出的概念，其根本思想是通过拆分原则，希望一个服务只负责业务中一个独立的功能，这样任何一个需求不会因为发布或者维护而影响到不相关的服务，所有服务都可以做到独立部署运维，当然这也只是微服务架构给我们带来的好处之一。但是：首先，原来的单个应用_istio

c语言课程图书信息管理系统,c语言课程设图书信息管理系统.doc-程序员宅基地

文章浏览阅读434次。c语言课程设图书信息管理系统课程设计报告课程：高级语言程序设计学号： 1010431059姓名：胡维维班级：嵌入式一班教师：王群芳时间： 2011年6月计算机科学与技术系设计名称：图书信息管理系统设计图书信息包括：登录号、书名、作者名、分类号、出版单位、出版时间、价格等。试设计一图书信息管理系统，使之能提供以下功能：1、图书信息录入功能2、图书信息浏览功能3、图书信息查询功能 ..._c语2、图书信息管理图书信息包括:登录号、书名、作者名、分类号、出版单位、出版

webpack4脚手架搭建1——打包并编译es6_webpack编译es6语法打包-程序员宅基地

文章浏览阅读695次。使用webpack执行webpack -h 查看webpack命令行使用说明安装webpack与webpack-cli安装webpack cnpm install webpack -g，安装后执行webpack -v会提示安装webpack-cli，这是因为在webpack 3中，webpack本身和它的CLI以前都是在同一个包中，但在第4版中，他们已经将两者分开来更好地管理它们。所以用 c..._webpack编译es6语法打包

信息通信服务、电子商务及物流服务的创新与发展_信息通信,电子商务-程序员宅基地

文章浏览阅读828次。2019年，国际互联网的蓬勃发展促使“物联网”（IoT）、云计算、大数据、人工智能等新兴技术的普及和应用。而在物流、电子商务、信息通信网络服务领域，亦或将成为信息时代最重要的基础设施。近几年，数字经济正走向成熟，用户的接受能力也越来越高，因此，信息通信服务、电子商务及物流服务都迎来了新的机遇。这些领域正经历着蓬勃的创新变革和不断变化，也是非常值得关注的领域。2020年，我国在推进“一带一路”倡议、开放世界经济格局方面取得重大成功，也促进了互联网和电子商务的发展。_信息通信,电子商务