二分查找-P2249 【深基13.例1】查找

文章目录

    • 参考代码
    • 二分标准模板

在这里插入图片描述

题目来源-洛谷网

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int m,n,a[N],b;
int find(int t)
{int l=1,r=n;while(l<r){int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) r=mid;//中间值比查找的值大或者相等,区间左移 else l=mid+1; }if(a[l]==t) return r;  //此时 l=r 都是要求的值 else return -1;
}
int main()
{int ans;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>b;ans=find(b);cout<<ans<<" ";}return 0;
}

如果要求的是输出编号的最大值
参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int m,n,a[N],b;
int ans; 
int find(int t)
{int l=1,r=n;while(l<r){int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]<=t) l=mid+1;//中间值比查找的值大或者相等,区间左移 else r=mid; }if(a[l-1]==t) return l-1;  //区间在右移 ,右端的值不会满足条件 else return -1;
}
int main()
{int ans;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>b;ans=find(b);cout<<ans<<" ";}return 0;
}

万能公式套用版

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int m,n,a[N],b;
int ans; 
int find(int t)
{int l=1,r=n;while(l<=r) //再求最小编号时,l r相邻 比如 133 一定要注意最小编号是否能拿到 {int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) {ans = mid; //记录值 r=mid-1; }else l=mid+1;}if(a[ans]==t) return ans;  else return -1;
}
int main()
{int ans;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>b;ans=find(b);cout<<ans<<" ";}return 0;
}

二分标准模板

int find(int t)
{int l=1,r=n;while(l<=r) //一定是相等{int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) {ans = mid; //记录值 r=mid-1; }else l=mid+1;}if(a[ans]==t) return ans;  else return -1;
}

求较小编号

int find(int t)
{int l=1,r=n;while(l<r) {int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) {r=mid; }else l=mid+1;}if(a[r]==t) return r;  //l也对else return -1;
}

求较大编号

int find(int t)
{int l=1,r=n;while(l<r) {int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]<=t) {l=mid+1;}else r=mid; }if(a[l-1]==t) return l-1;  //l会比准确值大些else return -1;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.pswp.cn/web/83065.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

手写muduo网络库(一):项目构建和时间戳、日志库

引言 本文作为手写 muduo 网络库系列开篇&#xff0c;聚焦项目基础框架搭建与核心基础工具模块设计。通过解析 CMake 工程结构设计、目录规划原则&#xff0c;结合时间戳与日志系统的架构&#xff0c;为后续网络库开发奠定工程化基础。文中附完整 CMake 配置示例及模块代码。 …

NLP学习路线图(三十二): 模型压缩与优化

一、 核心压缩与优化技术详解 1. 知识蒸馏:智慧的传承(Knowledge Distillation, KD) 核心思想:“师授徒业”。训练一个庞大、高性能但笨重的“教师模型”(Teacher Model),让其指导训练一个轻量级的“学生模型”(Student Model)。学生模型学习模仿教师模型的输出行为(…

vue前端字典映射

1.界面展示 2.图中状态字段接收的数据如下 3.代码转换&#xff0c;添加计算属性代码 再在绑定属性的地方做转换 computed: {statusMap() {return {"-1": "已退号",1: "挂号",2: "接诊",3: "已完诊",};},},<m-input:spa…

基于 llama-factory进行模型微调

# GLM4-9B-chat Lora 微调. 介绍如何基于 llama-factory 框架&#xff0c;对 glm-4-9b-chat 模型进行 Lora 微调。Lora 是一种高效微调方法&#xff0c;深入了解其原理可参见博客&#xff1a;[知乎|深入浅出 Lora](https://zhuanlan.zhihu.com/p/650197598)。 ## 环境配置 在完…

不到 2 个月,OpenAI 火速用 Rust 重写 AI 编程工具。尤雨溪也觉得 Rust 香!

一、OpenAI 用 Rust 重写 Codex CLI OpenAI 已用 Rust 语言重写了其 AI 命令行编程工具 Codex CLI&#xff0c;理由是此举能提升性能和安全性&#xff0c;同时避免对 Node.js 的依赖。他们认为 Node.js “可能让部分用户感到沮丧或成为使用障碍”。 Codex 是一款实验性编程代理…

Go 并发编程深度指南

Go 并发编程深度指南 Go 语言以其内置的并发原语而闻名&#xff0c;通过 goroutine 和 channel 提供了一种高效、安全的并发编程模型。本文将全面解析 Go 的并发机制及其实际应用。 核心概念&#xff1a;Goroutines 和 Channels 1. Goroutines (协程) Go 的轻量级线程实现&…

vue和uniapp聊天页面右侧滚动条自动到底部

1.vue右侧滚动条自动到底部 <div ref"newMessage1"></div> <!-- 定义<div ref"newMessage1"></div>与<div v-for”item in list“>循环同级定义-->定义方法 scrollToBottomCenter(){this.$nextTick(() > {this.$re…

iOS 项目怎么构建稳定性保障机制?一次系统性防错经验分享(含 KeyMob 工具应用)

崩溃、内存飙升、后台任务未释放、页面卡顿、日志丢失——稳定性问题&#xff0c;不一定会立刻崩&#xff0c;但一旦积累&#xff0c;就是“上线后救不回来的代价”。 稳定性保障不是某个工具的功能&#xff0c;而是一套贯穿开发、测试、上线全流程的“观测分析防范”机制。 …

JMeter函数整理

"_csvRead"函数 csvRead函数是从外部读取参数&#xff0c;csvRead函数可以从一个文件中读取多个参数。 下面具体讲一下如何使用csvread函数&#xff1a; 1.新建一个csv或者text文件&#xff0c;里面保存要读取的参数&#xff0c;每个参数间用逗号相隔。每行表示每一组…

深入理解 React Hooks

在当今的 React 开发中,Hooks 已经成为构建函数组件的核心工具。自 React 16.8 版本引入以来,Hooks 彻底改变了开发者编写 React 组件的方式,使得状态管理和副作用处理变得更加简洁和直观。本文将全面介绍 React 提供的各种 Hooks,从基础的 useState 和 useEffect,到高级的…

Doris-2:单虚拟机上非docker化安装Doris实验环境

Doris-2:单虚拟机上非docker化安装Doris实验环境 1.安装1.1.环境说明1.2.基础准备1.2.1.JDK1.2.2.操作系统配置(使用root或者有权账户)1.2.2.1.修改环境变量1.2.2.2.修改虚拟内存区域1.2.2.3.关闭swap1.2.2.4.关闭防火墙1.2.2.5.创建用户和组1.3.安装doris1.3.1.解压1.3.2.配置…

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…

Razor编程中@Helper的用法大全

文章目录 第一章&#xff1a;Helper基础概念1.1 Helper的定义与作用1.2 Helper的基本语法结构1.3 Helper与HtmlHelper的区别 第二章&#xff1a;基础Helper用法2.1 无参数Helper2.2 带简单参数的Helper2.3 带默认值的参数2.4 使用模型作为参数 第三章&#xff1a;高级Helper用法…

Python-正则表达式(re 模块)

目录 一、re 模块的使用过程二、正则表达式的字符匹配1. 匹配开头结尾2. 匹配单个字符3. 匹配多个字符4. 匹配分组5. Python 代码示例 三、re 模块的函数1. 函数一览表2. Python 代码示例1&#xff09;search 与 finditer2&#xff09;findall3&#xff09;sub4&#xff09;spl…

前端知识导图

前端知识导图 参考&#xff1a;字节标准 前端知识导图 通用基础 1、编程语言 HTML CSS JS TS 2、计算机基础 计算机网略 数据结构 算法&#xff1a;二分查找、十大排序、二叉树先中后和层次遍历、集合交并集、leetcode刷题经验 编译构建 webpack & vite 应用基础 开…

moon游戏服务器-demo运行

下载地址 https://github.com/sniper00/MoonDemo redis安装 Redis-x64-3.0.504.msi 服务器配置文件 D:\gitee\moon_server_demo\serverconf.lua 貌似不修改也可以的&#xff0c;redis不要设置密码 windows编译 安装VS2022 Community 下载premake5.exe放MoonDemo\server\moon 双…

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…

ajax学习手册

Ajax 通俗易懂学习手册 目录 Ajax 基础概念XMLHttpRequest 详解Fetch API (现代方式)处理不同数据格式错误处理和状态码Ajax 高级技巧实战项目案例最佳实践 Ajax 基础概念 什么是 Ajax&#xff1f; Ajax Asynchronous JavaScript And XML 通俗解释&#xff1a; Ajax 就像…

人工智能学习02-安装环境

人工智能学习概述—快手视频 人工智能学习02-安装—快手视频 Python安装 Python安装分为两种方法&#xff0c;一是从官网(https://www.python.org/)下载Python工具(比如python-2.7.msi)进行安装&#xff0c;并设置Path环境变量&#xff1b;二是下载工具Anaconda集成环境进行安…

电脑开不了机,主板显示67码解决过程

文章目录 现象分析内存条问题BIOS设置问题其它问题 解决清理内存条金手指所需工具操作步骤注意事项 电脑在运行过程中&#xff0c;显示内存不足&#xff0c;重启电脑却无法启动。 现象 System Initialization 主板风扇是转的&#xff0c;也有灯光显示&#xff0c;插上屏幕&am…