789. 数的范围 (二分学习)左端大右,右端小左

题目链接icon-default.png?t=N7T8https://www.acwing.com/file_system/file/content/whole/index/content/4317/

当求左端点时,条件是a【mid】大于等于x,并把右端点

当求右端点时,条件是a【mid】小于等于x,并把左端点。 

1.确定一个区间,使得目标值一定在区间中

2.找一个性质满足:

        (1)性质具有二段性

        (2)答案是二段性的分界点

3.整数二分(处理红色右端点和绿色左端点)

        

//代码1:右端点
int l=0,r=n;
while(l < r){
    int mid = (l+r+1) >> 1;
    if(在红色段){
        l = mid;
    }
    else r = mid - 1;
}
//代码2:左端点绿色
if是绿的,说明ans在【了,m】
int l=0,r=n;
while(l<r){
    int mid = l+r >> 1;
    if(是绿的){
        r = mid;
    }
    else l = mid + 1;
}

例题:

在这道题中,因为开始已经求出左端点了,所以求右端点时l可以不动,只更新r为n-1

0402重写:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;
//要求左边界右边界
int n;
int a[100010];
int q;

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    
    while(q--){
        int x;
        scanf("%d",&x);
        int l=0,r=n-1;
        while(l<r){
            int mid = l+r >> 1;
                    if(a[mid] >= x){
                        r = mid;
                    }
                    else{
                        l = mid + 1;
                    }
        }
        if(a[l] == x){
                printf("%d ",l);
                l = 0;
                r = n-1;
                while(l<r){
                     int mid = l+r+1 >> 1;
            if(a[mid] <= x){
                l = mid;
            }
            else r = mid - 1;
                   
                }
                if(a[l] == x){
                    printf("%d\n",l);
                }
            }
        else{
                printf("-1 -1\n");
            }
    }
    return 0;
}

代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;

int n,k;
int a[100010];

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    
    while(k--){
        int q;
        scanf("%d",&q);
        //找区间左端点
        int l=0,r=n-1;
        while(l<r){
            int mid = l+r >> 1;
            if(a[mid] >= q)//中位数大于q,说明右端点在左半段
            {
                r = mid;
            }
            else l = mid + 1;
        }
        if(a[l] == q){
            cout<<l<<" ";
            //右端点
            l = 0,r = n-1;
            while(l < r){
                int mid = (l + r + 1) >> 1;
                if(a[mid] <= q){
                    l = mid;
                }
                else r = mid - 1;
            }
            if(a[l] == q){
                cout<<l<<endl;
            }
        }
        else {
            cout<<"-1 -1"<<endl;
        }
    }
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

机器人力觉控制(力源)原理及力矩传感器性能分析

机器人力控原理及其性能分析 在机器人的操作任务中&#xff0c;处理机器人和环境之间的物理接触是非常重要的。由于机器人系统的复杂性和不确定性&#xff0c;纯运动控制往往是不够的&#xff0c;因为即使是最精确的模型也无法完全准确地预测所有可能的情况。 当机器人在与环境…

Qt5.15以上版本在线安装步骤,可选择更多早期版本

以ubuntu系统为例&#xff1a; 1、先去下载在线安装程序&#xff1a; https://download.qt.io/official_releases/online_installers/ 选择合适的版本&#xff0c;这里是在x64机器的ubuntu虚拟机里安装QT&#xff0c;所以选择如下版本&#xff1a; 或者直接在终端执行如下命令…

56.合并区间

这个C代码实现了一个名为Solution的类&#xff0c;其中有一个公共成员函数merge&#xff0c;该函数接收一个二维整数向量&#xff08;表示一系列闭区间&#xff09;&#xff0c;并返回一个新的二维整数向量&#xff0c;其中包含所有已合并的不重叠区间。 // 定义一个名为Solut…

【Java+Springboot】----- 通过Idea快速创建SpringBoot项目操作方法

一、第一步&#xff1a; 点击选择【File】->【New】-> 【Project】 最后弹出[new Project]界面。 二、第二步&#xff1a; 1. 选择【Spring Initializr】 2. 然后选择【Project SDK】的版本 3. 然后 Choose Initializr Service URL 选择默认&#xff08;Default&#x…

【漏洞复现】畅捷通T+ KeyInfoList.aspx SQL注入漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…

pcb封装的丝印大小

下面的内容是我自己的看法&#xff0c;观点不同欢迎评论区讨论。 个人结论&#xff1a; 0402:4.1*37 0603:5*45 0805:6.6*60 1206:10.5*95 设计PCB时常用的封装有0402、0603、0805、1206不同的封装我认为应该对应不同的丝印大小。便于后期维修焊接&#xff0c;但是具体用…

[挖坟]如何安装Shizuku和LSPatch并安装模块(不需要Root,非Magisk)

2023年12月13日&#xff0c;LSPatch 停止维护 2024年1月8日&#xff0c;LSPosed 停止维护 2024年1月8日&#xff0c;ZygiskNext 停止维护 2024年1月9日&#xff0c;KernelSU 停止维护 这里使用 ColorOS 14 演示&#xff0c;其他品牌手机类似 安装 Shizuku 官网: https://shiz…

【论文通读】AgentStudio: A Toolkit for Building General Virtual Agents

AgentStudio: A Toolkit for Building General Virtual Agents 前言AbstractMotivationFramework评估GUI GroudingReal-World Cross-Application Benchmark Suite Conclusion 前言 来自昆仑万象的一篇智能体环境数据大一统框架工作&#xff0c;对未来计算机智能体的发展具有指…

京东云服务器地域和可用区选择方法,多因素考虑攻略

京东云服务器地域如何选择&#xff1f;根据地理位置就近选择地域。京东云主机地域支持北京、宿迁、上海和广州&#xff0c;华北地区用户选择北京地域&#xff0c;华东地区用户可以选择上海或宿迁地区&#xff0c;南方用户选择广州地域。云服务器吧yunfuwuqiba.com整理京东云主机…

PCI总线学习笔记:读写篇

前言 最近在写E1000网卡的驱动&#xff0c;这其中涉及到了PCI总线的相关内容。但是网上大部分关于PCI的文章都只局限在概念上的描述&#xff0c;并没有给出具体的例子来解释。这其实也是情理之中的&#xff0c;因为PCI总线规范就像是一个抽象的接口&#xff0c;其具体怎么实现…

SnapGene:解码生命之链的强大工具 mac/win版

在生物科技日新月异的时代&#xff0c;DNA分析已成为众多科研领域不可或缺的工具。SnapGene DNA生物分析软件应运而生&#xff0c;以其强大的功能和直观的用户界面&#xff0c;赢得了众多科研人员的青睐。 SnapGene软件获取 SnapGene是一款功能全面的DNA序列分析工具&#xff…

DevC++进行调试时,控制台出来后就闪退怎么解决

工具->编译选项->代码生成->连接器&#xff0c;然后将调试信息改成yes就可以了 如果有帮助麻烦点个赞呗

【好书推荐-第十四期】《 互联网大厂晋升指南:从P5到P9的升级攻略》

&#x1f60e; 作者介绍&#xff1a;我是程序员洲洲&#xff0c;一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公众号&#xff1a;洲与AI。 &#x1f388; 本文专栏&#xff1a;本文收录…

0基础没编程经验能学嵌入式吗?

0基础没编程经验能学嵌入式吗&#xff1f; 可以的&#xff0c;即使你是0基础&#xff0c;没有编程经验&#xff0c;也完全有可能学习嵌入式系统。嵌入式系统是计算机技术与特定应用领域相结合的产物&#xff0c;涉及硬件和软件的知识。从零开始学习嵌入式开发&#xff0c;你可…

归并排序解读

在算法领域中&#xff0c;排序算法一直是一个核心话题。归并排序&#xff08;Merge Sort&#xff09;作为一种典型的分治思想应用&#xff0c;以其稳定、高效的特点受到了广泛的关注和应用。本文将深入探讨归并排序的原理、实现方式&#xff0c;以及它在实际应用中的价值。 一…

入门MyBatis

文章目录 入门MyBatisMyBatis快速入门创建user表添加数据创建模块导入坐标编写Mybatis核心配置文件编写SQL映射文件编码 使用idea编写sql代码链接数据库调出console控制台 Mapper代理开发定义与SQL映射文件同名的Mapper接口编码 MyBatis核心配置文件安装mybatisx插件配置文件完…

llama2的python视角

1 调试代码 if __name__ __main__ :config ModelArgs(dim8, n_layers2, n_heads32, n_kv_heads32, vocab_size32000, hidden_dimNone, multiple_of256, norm_eps1e-05, max_seq_len3, dropout0.0)model Transformer(config)input_tokens torch.randint(0, 32000, (1, 3)) …

【Linux】UDP编程【上】{诸多编程接口/小白入门式讲解}

文章目录 0.预备知识0.1套接字0.2TCP/UDP0.3大小端问题 1.socket 常见API1.1socket1.2各个接口1.3int bind();1.3网络头文件四件套1.4bzero1.5recvfrom1.6sendto() 2.UDP编程2.1服务器编程2.2客户端编程2.3运行测试2.3.1本机通信2.3.2popen2.3.3strcasestr2.3.4回顾C11智能指针…

靠劳保手套代加工赚钱 这几点一定要记牢

中国劳保手套代加工行业是一个与劳动保护密切相关的行业&#xff0c;随着中国经济的快速发展和安全生产意识的提高&#xff0c;劳保手套的需求呈现出稳步增长的趋势。得益于国内制造业、建筑业、矿业等劳动密集型行业的持续快速发展&#xff0c;中国劳保手套市场规模在过去几年…

路径规划——搜索算法详解(六):LPA*算法详解与Matlab代码

上文讲解了D*算法&#xff0c;D*算法为在动态环境下进行路径规划的场景提出了可行的解决方案&#xff0c;本文将继续介绍另外一种动态规划路径的方法——Lifelong Planning A*&#xff08;LPA*&#xff09;算法。 该算法可以看作是A*的增量版本&#xff0c;是一种在固定起始点…