当前位置: 首页 > 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;当用户未登录时…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

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

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

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...