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

【AcWing】1.1.3二分搜索

一、二分搜索

1、查找数的范围

  • 原题链接
    在这里插入图片描述
     这道题看似是二分搜索的题目,实则就是二分搜索。与一般的搜索不同的是,若查找元素重复,则分别返回重复元素的左端下标和右端下标,若不存在则返回“-1 -1。我们常用的二分搜索是返回的重复元素的左端下标,稍作修改,则可以返回右端元素下标。
#include<iostream>
#include<stdio.h>
using namespace std;
const int N = 1e5+10;
int a[N];//若存在重复元素,则返回左边界
int searchLeft(int q[],int l,int r,int x)
{while(l<r){int mid = l+r>>1;if(q[mid]<x){l = mid+1;}else{r = mid ;}}return l;
}
//若存在重复,则返回右边界
int searchRight(int q[],int l,int r,int x)
{while(l<r){int mid = (l+r+1)>>1;if(q[mid]<=x)l = mid;elser = mid-1;}return r;
}
int main()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}while(m--){int num;cin>>num;//搜索左边界int pos1 = searchLeft(a,0,n-1,num);//搜索有边界if (a[pos1]!=num){cout<<"-1 -1"<<endl;}else{int pos2 = searchRight(a,0,n-1,num);cout<<pos1<<' '<<pos2<<endl;}}system("pause");return 0;
}

2、数的三次方根

  • 原题链接
  • 在这里插入图片描述
     这道题可以用二分搜索的方法,来搜索一个数的三次方根的近似解。
#include<iostream>
using namespace std;
int main()
{double x,l = -100000.0,r = 100000.0;cin>>x;while(r-l>1e-8){double mid = (l+r)/2.0;if(mid*mid*mid< x){l = mid;}elser = mid;}printf("%.6f\n",r);return 0;
}

相关文章:

【AcWing】1.1.3二分搜索

一、二分搜索 1、查找数的范围 原题链接  这道题看似是二分搜索的题目&#xff0c;实则就是二分搜索。与一般的搜索不同的是&#xff0c;若查找元素重复&#xff0c;则分别返回重复元素的左端下标和右端下标&#xff0c;若不存在则返回“-1 -1。我们常用的二分搜索是返回的…...

【Python第三方包】串口通信(pySerial包)

文章目录 前言一、串口的基本使用1.1 配置串口基本信息1.2 读取串口数据1.3 写串口1.4 关闭串口二、示例代码2.1 示例1: 从串口读取数据2.2 示例2: 向串口写入数据总结前言 串口通信是许多嵌入式和物联网应用中的关键组成部分。Python 提供了许多第三方库来简化串口通信的实现…...

VS Code2023安装教程(最新最详细教程)附网盘资源

目录 一.简介 二.安装步骤 三.VS Code 使用技巧 网盘资源见文末 一.简介 VS Code是一个由微软开发的跨平台的轻量级集成开发环境&#xff08;IDE&#xff09;&#xff0c;被广泛用于编写各种编程语言的代码。它支持多种编程语言&#xff0c;并且可以通过插件扩展功能。 以…...

最优值函数

一、最优状态值函数 解决强化学习任务大致上意味着找到一种政策&#xff0c;能够在长期内实现很多奖励。对于有限MDPs&#xff0c;我们可以精确地定义一种最优政策&#xff0c;其定义如下。值函数定义了政策的一种部分排序。如果一个政策的预期回报大于或等于另一个政策π0在所…...

软考系统架构师知识点集锦十:计算机网络、数学与经济管理、知识产权与标准化

一、计算机网络 1.1、考情分析 2.1 TCP/IP协议簇 2.1.1常见协议及功能 网际层是整个TCP/IP体系结构的关键部分,其功能是使主机可以把分组发往任何网络并使分组独立地传向目标。 POP3: 110 端口&#xff0c;邮件收取SMTP: 25 端口&#xff0c;邮件发送FTP: 20数据端口/21控制…...

风云七剑攻略,最强阵容搭配

今天的风云七剑攻略最强阵容搭配给大家推荐以神仙斋减怒回血为主的阵容。 关注【娱乐天梯】&#xff0c;获取内部福利号 首先&#xff0c;这个角色在这个阵容当中&#xff0c;所有的角色当中&#xff0c;他的输出系数是最高的&#xff0c;已经达到了200%的层次&#xff0c;而且…...

关于ABB 机器人多任务的建立

关于ABB 机器人多任务的建立.需要实时监控某一区域&#xff0c;或者某一信号&#xff0c;或者计件到达某一数量机器人自动停止报警&#xff0c;显示到示教器上&#xff0c;多任务可以实现&#xff0c;类似发那科机器人后台逻辑指令 当软件选项漏选或者少选可以选择修改选项&…...

【计算机网络笔记】传输层——多路复用和多路分用

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…...

【PC】特殊空投-2023年10月

亲爱的玩家朋友们&#xff0c;大家好&#xff01; 10月特殊空投活动来袭。本月我们也准备了超多活动等着大家来体验。快来完成任务获得丰富的奖励吧&#xff01;签到活动&#xff0c;每周一次的PUBG空投节&#xff0c;还有可以领取PGC2023免费投票劵的活动等着大家&#xff01;…...

Android Studio 下载地址

一、Android Studio 下载地址及版本说明 1.Android 开发者官网&#xff1a;&#xff08;1&#xff09;Android Developers &#xff08;全球&#xff0c;需科学上网&#xff09; &#xff08;2&#xff09;https://developer.android.google.cn/index.html &#xff08;国内&a…...

General error: 2006 MySQL server has gone away thinkphp6.0 报这个错误怎么修改

"General error: 2006 MySQL server has gone away" 错误表示 MySQL 服务器连接已断开或超时&#xff0c;导致无法继续进行数据库操作。 在 ThinkPHP 6.0 中&#xff0c;您可以通过以下方法来解决这个问题&#xff1a; 调整 MySQL 服务器的超时设置&#xff1a;您可…...

08 _ 栈:如何实现浏览器的前进和后退功能?

浏览器的前进、后退功能,我想你肯定很熟悉吧? 当你依次访问完一串页面a-b-c之后,点击浏览器的后退按钮,就可以查看之前浏览过的页面b和a。当你后退到页面a,点击前进按钮,就可以重新查看页面b和c。但是,如果你后退到页面b后,点击了新的页面d,那就无法再通过前进、后退…...

【T】分治与倍增

分治&#xff0c;分而治之&#xff0c;其中最经典的便是二分 一、二分 一种经典而且非常好用的思想 将原问题对半转换成两个问题&#xff0c;子问题又继续转换成两个问题&#xff0c;许多子问题会很显然对答案没有关系&#xff0c;所以能讲原本O(n)的东西转化为O(logn) 但一般…...

后门分析及示例

代码分析&#xff0c;关键字定位 传一个asp文件 输入账户错误会提示&#xff1a;非法登录&#xff1b; 逆向工程抓取这个关键字定位 查找代码里面的关键字&#xff0c;定位到关键字后把代码复制出来&#xff0c; 修改exec执行函数为msgbox消息弹出用gb2312方式保存成VBS文件.…...

Vue 的双向数据绑定是如何实现的?

目录 1. 响应式数据 2. v-model 指令 3. 实现原理 4. 总结 Vue.js 是一款流行的前端 JavaScript 框架&#xff0c;它以其强大的双向数据绑定能力而闻名。双向数据绑定使得数据在视图和模型之间保持同步&#xff0c;并且任一方的变化都会自动反映到另一方。那么&#xff0c;…...

Android环境变量macOS环境变量配置

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 目录 一、导读二、概览macOS基础知识 三、设置环境变量3.1 终…...

设计模式(全23种)

1.前言 1.CUML类图 面向对象设计主要就是使用UML的类图&#xff0c;类图用于描述系统中所包含的类以及它们之间的相互关系&#xff0c;帮助人们简化对系统的理解&#xff0c;它是系统分析和设计阶段的重要产物&#xff0c;也是系统编码和测试的重要模型依据。下面基于C这门语…...

腾讯云轻量应用服务器“月流量”不够用怎么办?

腾讯云轻量应用服务器“月流量”不够用怎么办&#xff1f;超额部分支付流量费&#xff0c;价格为0.8元/GB。腾讯云轻量服务器月流量什么意思&#xff1f;月流量是指轻量服务器限制每月流量的意思&#xff0c;不能肆无忌惮地使用公网&#xff0c;流量超额需要另外支付流量费&…...

【esp32]VSCode-SPI控制OLED

根据Adafruit_GFX第三方库&#xff0c;其drawPixel方法由子类实现 代码&#xff1a;在OLED实现函数功能 先声明类 SPI库和Adafruit库、SSD1306 #include <Arduino.h> #include <SPI.h> #include <Adafruit_GFX.h> #include <Adafruit_SSD1306.h> …...

vue 的一些拦截

Vue.js 允许你在应用程序中进行路由和HTTP请求的拦截&#xff0c;以便在特定条件下执行操作或处理数据。以下是一些关于拦截的常见用例&#xff1a; 路由拦截&#xff1a; 你可以使用Vue Router来拦截路由导航。这通常用于权限控制&#xff0c;例如&#xff0c;当用户未登录时…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...