C++ 二分查找法【面试】
在C++中实现二分查找法是一个常见的面试问题。二分查找法是一种在有序数组中查找特定元素的算法,其时间复杂度为O(log n)。以下是使用C++实现二分查找的示例代码:
#include <iostream>
#include <vector>// 二分查找法函数
int binarySearch(const std::vector<int>& nums, int target) {int left = 0; // 定义左边界int right = nums.size() - 1; // 定义右边界while (left <= right) {int mid = left + (right - left) / 2; // 计算中间位置,防止溢出if (nums[mid] == target) {// 找到目标值,返回索引return mid;} else if (nums[mid] < target) {// 如果目标值大于中间值,更新左边界left = mid + 1;} else {// 如果目标值小于中间值,更新右边界right = mid - 1;}}// 未找到目标值,返回-1return -1;
}int main() {std::vector<int> nums = {-3, 10, 11, 21, 34, 54, 60, 78};int target = 21;int result = binarySearch(nums, target);if (result != -1) {std::cout << "Element found at index " << result << std::endl;} else {std::cout << "Element not found in the array." << std::endl;}return 0;
}
面试要点:
-
算法逻辑:解释二分查找的基本原理,包括如何确定中间位置,以及如何根据中间值与目标值的比较结果更新搜索范围。
-
数组要求:强调二分查找法要求数组是有序的。
-
时间复杂度:讨论二分查找的时间复杂度为O(log n),其中n是数组的大小。
-
防止溢出:在计算中间索引时使用
left + (right - left) / 2来防止整数溢出。 -
边界条件:说明循环条件是
while (left <= right),这保证了即使数组中只有一个元素,算法也能正确处理。 -
返回值:讨论函数的返回值,即找到目标时返回索引,未找到时返回-1。
面试回答示例:
"二分查找是一种高效的搜索算法,适用于有序数组。它的基本思想是将目标值与数组中间的元素进行比较。如果目标值等于中间元素,搜索成功;如果目标值小于中间元素,搜索范围缩小至数组的左半部分;如果目标值大于中间元素,搜索范围缩小至数组的右半部分。这个过程将重复,直到找到目标值或搜索范围为空。为了防止整数溢出,我们使用left + (right - left) / 2来计算中间索引。如果数组中有重复元素,二分查找将返回任意一个匹配的索引。"
相关文章:
C++ 二分查找法【面试】
在C中实现二分查找法是一个常见的面试问题。二分查找法是一种在有序数组中查找特定元素的算法,其时间复杂度为O(log n)。以下是使用C实现二分查找的示例代码: #include <iostream> #include <vector>// 二分查找法函数 int binarySearch(co…...
【Docker】docker-compose常用的构建docker容器的yml文件
docker-compose的简单使用方法,在准备好的文件夹中,mkdir好要挂载的如data或者conf文件夹,及vim docker-compose.yml,将下方的要使用的内容粘贴进去,根据自己需要添加/删除/修改一下。最后在当前文件夹直接后台启动即可…...
华为坤灵路由器初始化开局的注意事项,含NAT配置
坤灵路由器比较坑,无web界面,全程命令行配置,但是版本更新导致和华为企业路由器配置很多不一样的地方,今天介绍下 1、aaa密码复杂度修改: #使能设备对密码进行四选三复杂度检查功能。 <HUAWEI>system-view […...
HTTP!!!
HTTP 一 : 请求报文1.2 : 首行1.3 :请求头(header)1.4 : 空行1.5 : 正文 body 二: 响应报文2.2 : 首行 三 : URL 一 : 请求报文 一个HTTP 请求报文, 分成四个部分 首行 GET https://cn.bing.com/?FORMZ9FD1 HTTP/1.1请求头(header)空行正文(body) 1.2 : 首行 首行又分为三个…...
Mybatis用Map接收返回值可能出现的问题
先看一个示例 明明定义了Map<String,String> 实际内部存放的是Integer resultType是Map 也就是说Mybatis是通过反射将类型放进去的 躲过了编辑器检查 但是这样取值时候就会报类型转换错误 解决方式 resultMap 另外一种方式 用Number Integer和Double的父类 Ma…...
Web爬虫--fofa-资产信息搜集
免责声明:本文仅做技术交流与学习... 目录 fofa.py fofa搜索参数分析 fofa_api.py fofa.py import requests from bs4 import BeautifulSoup# 登录fofa之后,把自己的cookie弄过来. header{cookie: } # 参数为搜索的语法. urlhttps://fofa.info/result?qbase64dGl0bGU9IuS4…...
mySql的事务(操作一下)
目录 1. 简介2. 事务操作3. 四大特性4. 并发事务问题5. 脏读6. 不可重复读7. 幻读事务隔离级别参考链接 1. 简介 事务是一组操作的集合,它是一个不可分割的工作单位,事务会把所有的操作作为一个整体一起向系统提交或撤销操作请求,即这些操作…...
UniApp或微信小程序中scroll-view组件使用show-scrollbar在真机Android或IOS中隐藏不了滚动条的解决办法
show-scrollbar 属性 不论是使用 变量 还是直接使用 布尔值或者直接使用 css 都是在 ios、Android 上是都没有效果。。 真机中还是出现滚动条 解决办法 添加下面CSS ::-webkit-scrollbar {display: none;width: 0 !important;height: 0 !important;-webkit-appearance: no…...
每天五分钟深度学习框架pytorch:多维tensor向量在某一维度的拼接和分割
本文重点 在深度学习中,我们常常需要完成多个向量拼接,同时也要完成向量的分割,在pytorch中已经有封装好的库,我们可以直接调用完成这部分任务。 Cat拼接 c=torch.cat([a,b],dim=0)表示将a和b按0维度进行拼接,需要注意再非dim维度,两个矩阵的维度必须是一致的,不然会拼…...
从C语言到C++(五)
从C语言到C(五) 自动类型推导尾拖返回类型类型信息推导typeid1. 定义和基本作用2. 使用方法3. 注意事项4. 示例代码5. 关联概念:RTTI decltype基本用法示例注意事项总结 基于范围的增强for循环示例 1:使用数组示例 2:使…...
数据结构——栈(Stack)详解
1. 栈(Stack) 1.1 概念 栈:一种特殊的线性表,只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中数据元素遵循后进先出LIFO(Last In First Out)的原则 压栈&am…...
1.Element的table表高度自适应vue3+js写法
解决方法 在页面table上添加id,动态计算每页table的最大高度 ,将高度保存在store中,每次切换路由时进行计算。 文章目录 解决方法前言一、页面table使用二、store状态库1.引入库 效果 前言 提示:状态管理使用的是pinia,用法参考…...
联想电脑电池只能充到80%,就不在充电了,猛一看以为坏了,只是设置了养护模式。
现在电池管理模式有三种: 1)常规 2)养护 3)快充 好久没有用联想的电脑了,猛一看,咱充到了80%不充了,难道电池是坏的?我们要如何设置才可以让其充电到100%呢? 右下角…...
Unity接入PS5手柄和Xbox手柄以及Android平台的(以及不同平台分析)
Unity接入PS5手柄和Xbox手柄以及Android平台的(以及不同平台分析) 介绍Unity手柄小知识PC端和编辑器上的摇杆事件和滑动事件PS5手柄Xbox手柄北通手柄 安卓环境下(安卓手机或者安卓模拟器)PS5手柄Xbox手柄北通手柄 总结 介绍 最近…...
vue+java实现简易AI问答组件(基于百度文心大模型)
一、需求 公司想要在页面中加入AI智能对话功能,故查找免费gpt接口,最终决定百度千帆大模型(进入官网、官方文档中心); 二、主要功能列举 AI智能对话;记录上下文回答环境;折叠/展开窗口&#…...
刷代码随想有感(104):动态规划——01背包问题/二维dp数组
题干: 代码: #include<bits/stdc.h> using namespace std; int n,bagweight; void solve(){vector<int>weight(n, 0);vector<int>value(n, 0);for(int i 0; i < n; i){cin>>weight[i];}for(int j 0; j < n; j){cin>…...
Docker-Portainer可视化管理工具
Docker-Portainer可视化管理工具 文章目录 Docker-Portainer可视化管理工具介绍资源列表基础环境一、安装Docker二、配置Docker加速器三、拉取Portainer汉化版本镜像四、运行容器五、访问可视化界面 介绍 Portainer是一款开源的容器管理平台,它提供了一个直观易用的…...
SqlSugar 集成
1 关于 SqlSugar SqlSugar 是 .NET/C# 平台非常优秀的 ORM 框架,目前 Nuget 总下载突破 700K,Github 关注量也高达 3.2K,是目前当之无愧的国产优秀 ORM 框架之一。 SqlSugar 官方地址:果糖网 ( SqlSugar 官网 &#…...
MySQL Connector/C++ 和 MySQL Connector/ODBC 的区别
MySQL Connector/C++ 和 MySQL Connector/ODBC 是两种不同的数据库连接工具,它们各自有不同的特点和用途。以下是它们之间的一些主要区别: 1. **编程接口**: - MySQL Connector/C++ 提供了面向对象的编程接口,它是用C++编写的,提供了C++特有的类和对象来与MySQL数据库…...
Weevil-Optimizer象鼻虫优化算法的matlab仿真实现
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 Weevil-Optimizer象鼻虫优化算法的matlab仿真实现,仿真输出算法的优化收敛曲线,对比不同的适应度函数。 2.测试软件版本以及运行结果展示…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
本地部署drawDB结合内网穿透技术实现数据库远程管控方案
文章目录 前言1. Windows本地部署DrawDB2. 安装Cpolar内网穿透3. 实现公网访问DrawDB4. 固定DrawDB公网地址 前言 在数字化浪潮席卷全球的背景下,数据治理能力正日益成为构建现代企业核心竞争力的关键因素。无论是全球500强企业的数据中枢系统,还是初创…...
