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

备战蓝桥杯第一天【二分查找无bug版】

🌹作者:云小逸
📝个人主页:云小逸的主页
📝Github:云小逸的Github
🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前,其次就是现在!学会自己和解,与过去和解,努力爱自己。==希望春天来之前,我们一起面朝大海,春暖花开!==🤟
👏专栏:C++👏 👏专栏:Java语言👏
👏专栏:C语言初阶👏👏专栏:数据结构👏

文章目录

  • 前言
  • 二分查找【无bug版本】
  • 代码:
  • 例题:
    • 题目:
    • 输入格式
    • 输出格式
    • 数据范围
    • 输入样例:
    • 代码:
    • 在这里插入图片描述 ​
  • 最后


前言

今天这一篇文章写的是二分法的bug版适用于任何情况,如有错误,请私信告知我,十分感谢ε≡٩(๑>₃<)۶ 一心向学在这里插入图片描述

——————————————————————————————

首先先写上几句话:献给坚持创作的我和点开这篇文章希望进步的你
1.你过得快不快乐,只有你自己知道。其实谁都有一段不为人知的故事,其实谁都会脆弱的想要- -个停靠,其实谁都想和某个人完成曾经诺言,其实谁都能微笑然后转身流泪,其实谁都的生活都多少有那点苦涩,经历风雨。我只想要少一点悲伤悲伤,多一点快乐。我只想要少- -点孤独,多一点幸福。

2.不是所有的是非都能理清,不是所有的付出都有收获。有些选择是无可奈何,有些失去是注定的。与其无法言说,不如一-笑而过;与其无法释怀,不如安然自若。

3.所谓开心,就是眼睛向.上把快乐放大;所谓烦恼,就是眼睛向下把烦恼放大。

4.你若自信,就有微笑,你若看开,就有快乐,用纯净的眼光看世界,世界就是精彩的,用淡然的方式去生活,生活就是美好的,用平常的心态看得失,人生就是轻松的。

5.心存梦想,机遇就会笼罩着你;心存希望,幸福就会降临于你;心存坚持,快乐就会常伴你;心存真诚,平安就会跟随你;心存感恩,贵人就会青睐你;心存善念,阳光就会照耀你;心存美丽,温暖就会围绕你;心存大爱,崇高就会追随你;心存他人,真情就会回报你;美丽由心而定,心简单就会幸福!

二分查找【无bug版本】

二分查找法的思想在1946年提出的,第一个没有bug的二分查找法在1962年才出现。说明一个道理:真正的实现一个完全正确的算法是复杂的,只是思考算法的思想却是简单的。
在这里插入图片描述
借用acwing中y总的上课时的笔记:
在这里插入图片描述
注:
1.mid=l+r>>1;其是否加上1与后面check的内容以及true时是l=mid还是r=mid;
2.check(mid)是指q[mid]大于或者小于x,x是要查找的数。
3.这里有一个便于记忆的口诀:“有减必有加,有加不用减”如:
如果r=mid-1;则mid=(l+r+1)>>1;
如果l=mid+1;则mid=(l+r)>>1;
这里的口诀便于理解与记忆。

代码:

bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;    // check()判断mid是否满足性质else l = mid + 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}

例题:

题目:

给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。

对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。

如果数组中不存在该元素,则返回 -1 -1。

输入格式

第一行包含整数 n 和 q,表示数组长度和询问个数。

第二行包含 n 个整数(均在 1∼10000 范围内),表示完整数组。

接下来 q 行,每行包含一个整数 k,表示一个询问元素。

输出格式

共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。

如果数组中不存在该元素,则返回 -1 -1。

数据范围

1≤n≤100000

1≤q≤10000

1≤k≤10000

输入样例:

6 3
1 2 2 3 3 4
3
4
5

输出样例:

3 4
5 5
-1 -1

代码:

#include<iostream>
using namespace std;const int N=1e6+10;
int q[N];int main()
{int n=0,m=0;scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&q[i]);while(m--){int x=0;scanf("%d",&x);int l=0,r=n-1;while(l<r){int mid=l+r>>1;if(q[mid]>=x) r=mid;else l=mid+1;}if(q[l]!=x) cout<<"-1 -1"<<endl;else{cout<<l<<" ";int l=0,r=n-1;while(l<r){int mid=l+r+1>>1;if(q[mid]<=x) l=mid;else r=mid-1;}cout<<l<<endl;}}return 0;
}

在这里插入图片描述

最后

十分感谢你可以耐着性子把它读完和我可以坚持写到这里,送几句话,对你,也对我:

1.太多的事,慢慢地就不能做了;太多的人,渐渐地就不见了。成长似乎是一个丢失的过程。青春,就是注定了要颠簸,要有眼泪和汗水,有委屈、不甘和失败。后来,慢慢知道一切该发生的就是会发生,一切会错过的就是会错过。

2.趁自己还不老,走自己想走的路。没有理由,不去闯!时间,抓起了就是黄金,虚度了就是流水;理想,努力了才叫理想,放弃了那只是妄想!努力,虽然不一定会获得,但不努力,就一定一无所获。

3.趁自己还不老,走自己想走的路。没有理由,不去闯!时间,抓起了就是黄金,虚度了就是流水;理想,努力了才叫理想,放弃了那只是妄想!努力,虽然不一定会获得,但不努力,就一定一无所获。

4.我一直以为人是慢慢变老的,其实不是,人是一瞬间变老的。

5.随着年龄的增长,我们愈加发现,或许我们并不是失去了一些人,而是更加懂得到底谁才是最重要的人。

最后如果觉得我写的还不错,请不要忘记点赞✌,收藏✌,加关注✌哦(。・ω・。)

愿我们一起加油,奔向更美好的未来,愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油,为自己点赞!

相关文章:

备战蓝桥杯第一天【二分查找无bug版】

&#x1f339;作者:云小逸 &#x1f4dd;个人主页:云小逸的主页 &#x1f4dd;Github:云小逸的Github &#x1f91f;motto:要敢于一个人默默的面对自己&#xff0c;强大自己才是核心。不要等到什么都没有了&#xff0c;才下定决心去做。种一颗树&#xff0c;最好的时间是十年前…...

Java集合中的Map

MapMap接口键 值 对存储键不能重复&#xff0c;值可以重复Map三个实现类的存储结构HashMap&#xff1a;Hash表链表红黑树结构 线程不安全TreeMap&#xff1a; 底层红黑树实现HashTable&#xff1a;hash表链表红黑树 线程安全HashMapHashMap常用方法HashMap<String,String>…...

【java】springboot项目启动数据加载内存中的三种方法

文章目录一、前言二、加载方式2.1、 第一种&#xff1a;使用PostConstruct注解&#xff08;properties/yaml文件&#xff09;。2.2、 第二种&#xff1a;使用Order注解和CommandLineRunner接口。2.3、 第三种&#xff1a;使用Order注解和ApplicationRunner接口。三、代码示例3.…...

【GO】29.go-gin支持ssl/tls,即https示例

本文为演示采用自签名证书一.生成证书通过openssl工具生成证书1.1 安装opensslmacos通过brew安装brew install openssl1.2 生成跟证书私钥openssl genrsa -out ca.key 40961.3 准备配置文件vim ca.conf内容如下[ req ] default_bits 4096 distinguished_name req_disti…...

逻辑仿真工具VCS的使用-Makefile

Gvim写RTL code&#xff0c;VCS仿真&#xff0c;Verdi看波形&#xff0c;DC做综合下约束&#xff0c;Primetime做STA&#xff0c;Spyglass做异步时序分析。 VCS全称Verilog Computer Simulation &#xff0c;VCS是逻辑仿真EDA工具的编译源代码的命令。要用VCS做编译仿…...

信息系统安全技术

一、信息安全的有关概念 1. 属性2. 四个安全层次※3. 信息安全保护等级※4. 安全保护能力的等级※ 二、信息加密、解密与常用算法 1. 对称加密2. 非对称加密3. Hash函数4. 数字签名5. 认证 三、信息系统安全 1. 计算机设备安全2. 网络安全3. 操作系统安全4. 数据库安全5. 应用系…...

【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)

文章目录前置问题问题解答一、基础概念&#xff1a;最小生成树的定义和性质&#xff08;1&#xff09;最小生成树&#xff08;Minimal Spanning Tree&#xff09;的定义&#xff08;2&#xff09;最小生成树&#xff08;MST&#xff09;的性质二、如何利用MST性质寻找最小生成树…...

Session与Cookie的区别(一)

从我刚开始学程序时这一题就常出现在面试考题里&#xff0c;一直到现在都还是能看见这个问题。 这个问题重要吗&#xff1f;我觉得蛮重要的。因为 Session 所代表的是「状态」&#xff0c;如果没有了状态&#xff0c;一大堆功能都会失效。 对于工程师来说必须去理解什么是 Sess…...

【Java】重载和重写的区别

重载(Overload) 在同一个类中&#xff0c;同名的方法如果有不同的参数列表&#xff08;参数类型不同、参数个数不同甚至是参数顺序不同&#xff09;则视为重载。同时&#xff0c;重载对返回类型没有要求&#xff0c;可以相同也可以不同&#xff0c;但不能通过返回类型是否相同…...

AcWing 第 90 场周赛

目录A、首字母大写B、找数字C、构造字符串A、首字母大写 原题链接&#xff1a;AcWing 4806. 首字母大写 签到题。 #include <bits/stdc.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s;cin >> s;s[0] toupper(s[0]);…...

刚刚,体验了一把Bing chat很爽

文章目录刚刚&#xff0c;体验了一把Bing chat很爽你能做啥&#xff1f;与chatgpt有什么不同&#xff1f;以下是Bingchat的 10个新功能1⃣️在网上搜索结果2⃣️摘要链接3⃣️对话助手4⃣️向您发送实际信息&#xff0c;正确的链接5⃣️在单个查询中执行多个搜索6⃣️玩冒险游戏…...

牛客网Python篇数据分析习题(二)

1.现有一个Nowcoder.csv文件&#xff0c;它记录了牛客网的部分用户数据&#xff0c;包含如下字段&#xff08;字段与字段之间以逗号间隔&#xff09;&#xff1a; Nowcoder_ID&#xff1a;用户ID Level&#xff1a;等级 Achievement_value&#xff1a;成就值 Num_of_exercise&a…...

如何用Python打包好exe文件,并替换图标

前言 Python打包&#xff1f;打包exe文件&#xff1f;怎么操作&#xff1f; ok&#xff0c;今天我来分享分享&#xff0c;教你们如何打包号文件&#xff0c;顺便还来展示一下&#xff0c;如何替换好图标 首先把你的代码准备好&#xff0c;尽量不要中文路径&#xff0c;容易报…...

NFC概述摘要

同学,别退出呀,我可是全网最牛逼的 WIFI/BT/GPS/NFC分析博主,我写了上百篇文章,请点击下面了解本专栏,进入本博主主页看看再走呗,一定不会让你后悔的,记得一定要去看主页置顶文章哦。 原理来说,NFC和Wi-Fi类似,利用无线射频技术来实现设备间通信。NFC的工作频率为13.5…...

Python-项目实战--贪吃蛇小游戏(1)

1.贪吃蛇游戏规则贪吃蛇游戏规则如下:1.1开始和结束贪吃蛇初始出现在游戏窗口的左上角位置,体长共有3节游戏过程中&#xff0c;一旦蛇头撞到了窗口的边缘或者身体的其他部位,游戏结束游戏过程中&#xff0c;点击游戏窗口的关闭按钮&#xff0c;或者按下ESC键可以直接退出游戏一…...

vscode sftp从linux服务器下载文件至本地:No such file or dictionary【已解决】

在服务器跑完程序需要下载数据的时候报错&#xff1a; [warn] ENOENT: no such file or directory, open /home/LIST_2080Ti/.ssh/config load /home/LIST_2080Ti/.ssh/config failed 完整报错内容如下&#xff1a; [02-10 08:38:47] [info] config at /home/LIST_2080Ti {&q…...

详解指针(2)(初阶版)

前言&#xff1a;内容包括&#xff1a;指针运算&#xff0c;指针和数组&#xff0c;二级指针&#xff0c;指针数组 详解指针&#xff08;1&#xff09;&#xff08;点击即跳转&#xff09; part 1&#xff1a;指针运算 1 指针-整数 以如下代码为例&#xff1a;初始化数组内容…...

超详细讲解字符串查找函数(保姆级教程!!!)

超详细讲解字符串查找函数&#xff08;保姆级教程&#xff01;&#xff01;&#xff01;&#xff09;字符串查找函数strstr函数strstr函数的使用strstr函数的模拟实现strtok函数strtok函数的使用strtok函数的模拟实现strpbrk函数strpbrk函数的使用strpbrk函数的模拟实现strcspn…...

LeetCode-1138. 字母板上的路径【哈希表,字符串】

LeetCode-1138. 字母板上的路径【哈希表&#xff0c;字符串】题目描述&#xff1a;解题思路一&#xff1a;首先考虑坐标位置&#xff0c;字符是有序的从0开始&#xff0c;当前字符c的行为(c-a)/5,列为(c-a)%5。其次是考虑特殊情况z。若当前从‘z’开始则只能往上走;若是其他字符…...

Vue 可配置化的路由缓存(Vu2 Vue3)

Vue 可配置化的路由缓存&#xff08;Vu2 & Vue3&#xff09; 1 介绍 在Vue的项目当中&#xff0c;路由缓存是一个比较常见的功能&#xff0c;譬如&#xff0c;从列表页面进入到详情页面&#xff0c;返回到列表页面时&#xff0c;如果可以保持列表的状态&#xff0c;那用户…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

李沐--动手学深度学习--GRU

1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...

【技巧】dify前端源代码修改第一弹-增加tab页

回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码&#xff0c;在知识库增加一个tab页"HELLO WORLD"&#xff0c;完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...