当前位置: 首页 > news >正文

C++ 算法——二分查找

如果要你在一个升序序列中查找一个值的位置,你是否还会傻乎乎的用下面这个 O ( n ) \mathcal O(n) O(n) 的代码暴力查找,如果是,我告诉你,其实根本不用这么做。

int find(int a[],int n,int k) {for(int i=0;i<n;++i) if(a[i]==k) return i;
}

猜数字这个游戏大家都玩过吧,这里介绍以下规则:

  1. 一名玩家在一个范围内想出一个数。
  2. 这名玩家告诉其他玩家他所想的范围。
  3. 其他玩家在这个范围内猜数,若:
    • 猜中了:该玩家获胜
    • 没猜中:根据该玩家猜的数缩小范围,然后接着进行操作 2。对于缩小范围,设初始范围为 l ∼ y l\sim y ly,要猜的数为 n n n,猜的数位 n n n,若:
      • m < n m<n m<n,将范围缩小至 m ∼ r m\sim r mr
      • m > n m>n m>n,将范围缩小至 l ∼ m l\sim m lm

显然,想要最快猜到该数,就需要采用折半的方法去猜,每次都猜这个范围的中间数。二分查找也是一样,对于每一次查找,都判断中间的数与要找的数的大小关系,然后采取对应的操作。

需要注意的是,二分查找需要保证序列是升序的。

这里放个代码:

//循环版
int find(int a[],int n,int k) {int l=0,r=n-1;while(l<=r) {int mid=(l+r)/2;if(a[mid]>k) r=mid-1;else if(a[mid]<k) l=mid+1;else if(a[mid]==k) return mid;}return -1;
}
//递归版
int find(int a[],int n,int k,int l,int r) {if(l>r) return -1;int mid=(l+r)/2;if(a[mid]>k) return find(a,n,k,l,mid-1);else if(a[mid]<k) return find(a,n,k,mid+1,r);else if(a[mid]==k) return mid;
}

练习题:洛谷 link

相关文章:

C++ 算法——二分查找

如果要你在一个升序序列中查找一个值的位置&#xff0c;你是否还会傻乎乎的用下面这个 O ( n ) \mathcal O(n) O(n) 的代码暴力查找&#xff0c;如果是&#xff0c;我告诉你&#xff0c;其实根本不用这么做。 int find(int a[],int n,int k) {for(int i0;i<n;i) if(a[i]k)…...

【自动驾驶仿真在做什么——初学者总结(陆续补充)】

文章目录 基础概念自动驾驶级别再稍提一下ODD是什么&#xff1f; 自动驾驶仿真分类软件在环仿真硬件仿真 仿真究竟难在哪&#xff1f;关于lidar和radar区别一些名词解释 最近也是学习自动驾驶仿真相关知识&#xff0c;习惯去总结一下&#xff0c;方便自己回顾和总结&#xff0c…...

探索HTML5的设计原则:引领Web开发的未来方向

随着互联网的飞速发展&#xff0c;HTML5作为Web技术的核心标准之一&#xff0c;不仅极大地丰富了网页的表现力和交互性&#xff0c;还推动了Web应用向更加动态、高效、安全的方向迈进。HTML5的设计原则&#xff0c;体现了对用户体验、内容可访问性、跨平台兼容性以及未来可扩展…...

力扣喜刷刷--day1

1.无重复字符的最长子串 知识点&#xff1a;滑动窗口 基本概念 窗口&#xff1a;窗口是一个连续的子序列&#xff0c;可以是固定长度或可变长度。滑动&#xff1a;窗口在数据序列上移动&#xff0c;可以是向左或向右。边界&#xff1a;窗口的起始和结束位置。 应用场景 字符…...

配置linux的yum镜像为阿里镜像源

1.备份当前的yum源 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.backup 2.下载新的CentOS-Base.repo 到/etc/yum.repos.d wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo 3.清空并生成缓存 yum clean …...

react使用markdown进行展示

有一些文档非常长&#xff0c;但是又要挨个设置样式&#xff0c;直接用 组件库 - marked 注意文档要放在public下才能读取。但非常方便 import { marked, Renderer } from "marked".....const [html, setHtml] useState<any>("")const renderer:…...

实时温湿度监测系统:Micropython编码ESP32与DHT22模块的无线数据传输与PC端接收项目

实时温湿度监测系统 前言项目目的项目材料项目步骤模拟ESP32接线连接测试搭建PC端ESP32拷录环境对ESP32进行拷录PC端搭建桌面组件本地数据接收桌面小组件部分 实验总结 前言 人生苦短&#xff0c;我用Python。 由于我在日常工作中经常使用Python&#xff0c;因此在进行该项目…...

CloudWatch Logs Insights 详解

CloudWatch Logs Insights 是 AWS 提供的强大日志分析工具,允许您快速、交互式地搜索和分析日志数据。本文将详细介绍使用 CloudWatch Logs Insights 所需的权限、常用查询方法,以及一些实用的查询示例。 1. 所需权限 要使用 CloudWatch Logs Insights,用户需要具备以下 I…...

Jmeter在信息头中设置Bearer与 token 的拼接值

思路&#xff1a;先获取token&#xff0c;将token设置成全局变量&#xff0c;再与Bearer拼接。 第一步&#xff1a;使用提取器将token值提取出来&#xff0c;使用setProperty函数将提取的token值设置成全局变量&#xff0c;在登录请求后面添加BeanShell取样器 或者 BeanShell后…...

C#程序调用Sql Server存储过程异常处理:调用存储过程后不返回、不抛异常的解决方案

目录 一、代码解析&#xff1a; 二、解决方案 1、增加日志记录 2、异步操作 注意事项 3、增加超时机制 4、使用线程池 5、使用信号量或事件 6、监控数据库连接状态 在C#程序操作Sql Server数据库的实际应用中&#xff0c;若异常就会抛出异常&#xff0c;我们还能找到异…...

数据统计与数据分组18-25题(30 天 Pandas 挑战)

数据统计与数据分组 1. 知识点1.18 分箱与统计个数1.19 分组与求和统计1.20 分组获取最小值1.21 分组获取值个数1.22 分组与条件查询1.23 分组与条件查询及获取最大值1.24 分组及自定义函数1.25 分组lambda函数统计 2. 题目2.18 按分类统计薪水&#xff08;数据统计&#xff09…...

Apache Seata应用侧启动过程剖析——注册中心与配置中心模块

本文来自 Apache Seata官方文档&#xff0c;欢迎访问官网&#xff0c;查看更多深度文章。 本文来自 Apache Seata官方文档&#xff0c;欢迎访问官网&#xff0c;查看更多深度文章。 Apache Seata应用侧启动过程剖析——注册中心与配置中心模块 前言 在Seata的应用侧&#xf…...

大话光学原理:1.“实体泛光说”、反射与折射

一、实体泛光说 在古希腊&#xff0c;那些喜好沉思的智者们中&#xff0c;曾流传着一个奇妙的设想&#xff1a;他们认为&#xff0c;我们的眼睛仿佛伸出无数触手般的光线&#xff0c;这些光线能向四面八方延伸&#xff0c;紧紧抓住周围的每一个物体。于是&#xff0c;当我们凝视…...

住宅代理、移动代理和数据中心代理之间的区别

如果您是一名认真的互联网用户&#xff0c;可能需要反复访问某个网站或服务器&#xff0c;可能是为了数据抓取、价格比较、SEO 监控等用例&#xff0c;而不会被 IP 列入黑名单或被 CAPTCHA 阻止。 代理的工作原理是将所有传出数据发送到代理服务器&#xff0c;然后代理服务器将…...

光学传感器图像处理流程(一)

光学传感器图像处理流程&#xff08;一&#xff09; 1. 处理流程总览2. 详细处理流程2.1. 图像预处理2.1.1. 降噪处理2.1.2. 薄云处理2.1.3. 阴影处理 2.2. 辐射校正2.2.1. 辐射定标2.2.2. 大气校正2.2.3. 地形校正 2.3. 几何校正2.3.1. 图像配准2.3.2. 几何粗校正2.3.3. 几何精…...

el-table 树状表格查询符合条件的数据

需要对el-table的树状表格根据输入机构名称&#xff0c;筛选出符合条件的数据&#xff0c;可用如下方法&#xff1a; 页面内容如下&#xff1a; <el-input v-model"ogeName" placeholder"请输入机构名称"><el-table :data"list" row…...

MQTT教程--服务器使用EMQX和客户端使用MQTTX

什么是MQTT MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;是一种轻量级、基于发布-订阅模式的消息传输协议&#xff0c;适用于资源受限的设备和低带宽、高延迟或不稳定的网络环境。它在物联网应用中广受欢迎&#xff0c;能够实现传感器、执行器和其它设备…...

326. 3 的幂

哈喽&#xff01;大家好&#xff0c;我是奇哥&#xff0c;一位专门给面试官添堵的职业面试员 文章持续更新&#xff0c;可以微信搜索【小奇JAVA面试】第一时间阅读&#xff0c;回复【资料】更有我为大家准备的福利哟&#xff01; 文章目录 一、题目二、答案三、总结 一、题目 …...

多标签问题

一、多标签问题与单标签问题的区别&#xff1a; 多标签问题是单标签问题的推广。 举个例子&#xff0c;同时识别图片中的小汽车&#xff0c;公交车&#xff0c;行人时&#xff0c;标签值有三个&#xff1a;小汽车&#xff0c;公交车&#xff0c;行人。 单标签问题仅对一个标签…...

suricata7 rule加载(三)加载options

suricata7.0.5 加载options (msg:“HTTP Request Example”; flow:established,to_server; http.method; content:“POST”; http.uri; content:“query.php”; bsize:>9; http.protocol; content:“HTTP/1.1”; bsize:8; http.host; content:“360”; bsize:>3; class…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...