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

二分【1】二分查找框架 查找指定元素

目录

二分查找 基本思想

 几种情况汇总

一。严格递增序列

1.查找本身

2.查找第一个大于等于自己的 

3.查找第一个大于自己的

4.严格递减序列

二。有重复元素

1.取其中第一个出现的

2.取其中最后一个出现的


二分查找 基本思想

 几种情况汇总

一。严格递增序列

1.查找本身

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<=right){mid=left+(right-left)/2;if(num[mid]>x) right=mid-1;if(num[mid]<x) left=mid+1;if(num[mid]==x){for(int i=mid;i>0;i--)if(num[i]==x&&num[i-1]!=x) return i;}}return -1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

2.查找第一个大于等于自己的 

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<right){mid=left+(right-left)/2;if(num[mid]>x||num[mid]==x) right=mid;if(num[mid]<x) left=mid+1;}if(num[left]>=x) return left;else return left+1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

3.查找第一个大于自己的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<right){mid=left+(right-left)/2;if(num[mid]>x) right=mid;if(num[mid]<x||num[mid]==x) left=mid+1;}if(num[left]>x) return left;else return left+1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

4.严格递减序列

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<=right){mid=left+(right-left)/2;if(num[mid]>x) left=mid+1;if(num[mid]<x) right=mid-1;if(num[mid]==x) return mid;}return -1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

二。有重复元素

1.取其中第一个出现的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<=right){mid=left+(right-left)/2;if(num[mid]>x) right=mid-1;if(num[mid]<x) left=mid+1;if(num[mid]==x){for(int i=mid;i>0;i--)if(num[i]==x&&num[i-1]!=x) return i;return 0;}}return -1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

2.取其中最后一个出现的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<=right){mid=left+(right-left)/2;if(num[mid]>x) right=mid-1;if(num[mid]<x) left=mid+1;if(num[mid]==x){for(int i=mid;i>0;i--)if(num[i]==x&&num[i-1]!=x) return i;return 0;}}return -1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

相关文章:

二分【1】二分查找框架 查找指定元素

目录 二分查找 基本思想 几种情况汇总 一。严格递增序列 1.查找本身 2.查找第一个大于等于自己的 3.查找第一个大于自己的 4.严格递减序列 二。有重复元素 1.取其中第一个出现的 2.取其中最后一个出现的 二分查找 基本思想 几种情况汇总 一。严格递增序列 1.查找本身…...

Python 中如何使用 lambda 函数

在 Python 中&#xff0c;可以使用 lambda 函数来创建匿名函数。lambda 函数的语法是&#xff1a;lambda 参数: 表达式。以下是一些使用 lambda 函数的例子&#xff1a; 通过 lambda 函数来计算两个数的和&#xff1a; add lambda x, y: x y print(add(2, 3)) # 输出 5通过…...

关于焊点检测(SJ-BIST)模块实现

关于焊点检测&#xff08;SJ-BIST&#xff09;模块实现 语言 &#xff1a;Verilg HDL 、VHDL EDA工具&#xff1a;ISE、Vivado、Quartus II 关于焊点检测&#xff08;SJ-BIST&#xff09;模块实现一、引言二、焊点检测功能的实现方法&#xff08;1&#xff09; 输入接口&#x…...

关于修改Python中pip默认安装路径的终极方法

别想了&#xff0c;终极方法就是手动复制&#xff0c;不过我可以给你参考一下手动复制的方法 关于手动移动pip安装包的方法 别想了&#xff0c;终极方法就是手动复制&#xff0c;不过我可以给你参考一下手动复制的方法一、首先确认一下pip默认安装路径二、再确认一下需要移动到…...

android集成百度文心一言实现对话功能,实战项目讲解,人人都能拥有一款ai应用

大家好&#xff0c;今天给大家讲解下如何实现一个基于百度文心一言的app功能&#xff0c;app内部同时集成了讯飞的语音识别。本文适用于有android基础的小伙伴阅读&#xff0c;文章末尾放上本项目用到的全部实例代码&#xff0c;在使用前请务必看完本文章。 先来给大家看看效果…...

事件总线vueEvent

一个组件结束后要更新另一个组件数据&#xff0c;但是另一个组件和这个组件没有上下级关系 在 Vue 中&#xff0c;非父子组件之间进行通信通常需要使用事件总线或者其他的全局事件管理器。vueEvent 似乎是一个事件总线对象&#xff0c;通过 emit 方法触发了名为 updateData 的事…...

设计模式之观察者模式ObserverPattern(十一)

一、概述 观察者模式 (Observer Pattern) 是一种行为型设计模式&#xff0c;又被称为发布-订阅 (Publish/Subscribe) 模式&#xff0c;它定义了对象之间的一种一对多的依赖关系&#xff0c;使得当一个对象的状态发生变化时&#xff0c;所有依赖于它的对象都会自动收到通知并更新…...

JavaScript 编程语言【 数据类型】日期和时间

文章目录 日期和时间创建访问日期组件设置日期组件自动校准&#xff08;Autocorrection&#xff09;日期转化为数字&#xff0c;日期差值Date.now()基准测试&#xff08;Benchmarking&#xff09;对字符串调用 Date.parse总结✅任务创建日期显示星期数欧洲的星期表示方法许多天…...

RabbitMQ简单使用方法,以异步处理日志为例:

在RabbitMQ中异步记录日志的实现可以分为生产者将日志消息发送到队列&#xff0c;以及消费者从队列中取出消息并记录日志。当搭建好消息队列后&#xff0c;需要确保消费者持续运行&#xff0c;以便随时处理新进入的日志消息。 步骤一&#xff1a;设置生产者发送日志消息到Rabb…...

二分+模拟,CF1461D - Divide and Summarize

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 1461D - Codeforces 二、解题报告 1、思路分析 我们发现每次分裂操作结果都是固定的 我们从初始序列分裂出两个确定的子序列&#xff0c;两个确定的子序列又分裂出4个确定的子序列 那么也就是说…...

C#操作MySQL从入门到精通(16)——使用子查询

前言: 我们在查询数据的过程中有时候查询的数据不是从数据库中来的,而是从另一个查询的结果来的,这时候就需要使用子查询,本文使用的测试数据如下: 1、子查询 下面的代码就是先查询地址是安徽和广西的学生年龄,然后获取年龄对应的姓名 private void button__SubQuery…...

【vue实战项目】通用管理系统:图表功能

目录 前言 1.概述 2.数据概览页 2.1.柱状图 2.2.折线图 2.3.地图 前言 本文是博主前端Vue实战系列中的一篇文章&#xff0c;本系列将会带大家一起从0开始一步步完整的做完一个小项目&#xff0c;让你找到Vue实战的技巧和感觉。 专栏地址&#xff1a; https://blog.csd…...

第99天:权限提升-数据库提权口令获取MYSQLMSSQLOracleMSF

案例一&#xff1a;提权条件-数据库帐号密码获取方式 提权条件 - 数据库帐号密码获取方式 0 、网站存在高权限 SQL 注入点 1 、数据库的存储文件或备份文件 2 、网站应用源码中的数据库配置文件 3 、采用工具或脚本爆破 ( 需解决外联问题 ) sql注入点 xhcms后台管理系统…...

Java 环境配置 -- Java 语言的安装、配置、编译与运行

大家好&#xff0c;我是栗筝i&#xff0c;这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 002 篇文章&#xff0c;在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验&#xff0c;并希望进…...

升级最新版openssh-9.7p1及openssl-1.1.1h详细步骤及常见问题总结

近期因为openssh相继被漏洞扫描工具扫出存在漏洞&#xff0c;所以考虑升级操作系统中的openssh和openssl为最新版本&#xff0c;来避免漏洞风险。期间的升级过程及遇到的疑难问题&#xff0c;特此记录下来&#xff0c;供有需要的人参考。 本次目标是升级 openssh 为 9.7p1 版本…...

学习使用 Frida 过程中出现的问题

一、adb shell命令报错&#xff1a;error: no devices found 目前该问题解决方法仅供参考&#xff0c;可先看看再选择试试&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 查看此电脑也会发现没有出现手机型号文件夹。 第一步&#xff1a; 检查一下手机开了u…...

Java实现简单词法、语法分析器

1、词法分析器实现 词法分析器是编译器中的一个关键组件&#xff0c;用于将源代码解析成词法单元。 词法分析器的结构与组件&#xff1a; 通常&#xff0c;词法分析器由两个主要组件构成&#xff1a;扫描器&#xff08;Scanner&#xff09;和记号流&#xff08;Token Stream&a…...

Python实现半双工的实时通信SSE(Server-Sent Events)

Python实现半双工的实时通信SSE&#xff08;Server-Sent Events&#xff09; 1 简介 实现实时通信一般有WebSocket、Socket.IO和SSE&#xff08;Server-Sent Events&#xff09;三种方法。WebSocket和Socket.IO是全双工的实时双向通信技术&#xff0c;适合用于聊天和会话等&a…...

python中的解包操作(*和**)

在Python中&#xff0c;* 和 ** 用于函数定义和函数调用时的参数解包和传递&#xff0c;它们有不同的用途和作用。以下是它们的详细解释和区别&#xff1a; 单星号 (*) 1. 位置参数解包&#xff08;函数调用&#xff09; 在函数调用时&#xff0c;* 用于将列表或元组解包成位…...

Lua 时间工具类

目录 一、前言 二、函数介绍 1.DayOfWeek 枚举定义 2.GetTimeUntilNextTarget 3.GetSpecificWeekdayTime 三、完整代码 四、总结 一、前言 当我们编写代码时&#xff0c;我们经常会遇到需要处理日期和时间的情况。为了更方便地处理这些需求&#xff0c;我们可以创建一个…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

【Zephyr 系列 16】构建 BLE + LoRa 协同通信系统:网关转发与混合调度实战

🧠关键词:Zephyr、BLE、LoRa、混合通信、事件驱动、网关中继、低功耗调度 📌面向读者:希望将 BLE 和 LoRa 结合应用于资产追踪、环境监测、远程数据采集等场景的开发者 📊篇幅预计:5300+ 字 🧭 背景与需求 在许多 IoT 项目中,单一通信方式往往难以兼顾近场数据采集…...

若依项目部署--传统架构--未完待续

若依项目介绍 项目源码获取 #Git工具下载 dnf -y install git #若依项目获取 git clone https://gitee.com/y_project/RuoYi-Vue.git项目背景 随着企业信息化需求的增加&#xff0c;传统开发模式存在效率低&#xff0c;重复劳动多等问题。若依项目通过整合主流技术框架&…...