每周一算法:倍增法查找位置

倍增法

倍增法(Binary Lifting),顾名思义,就是利用“以翻倍的速度增长”的思想来解决问题的一类算法。

下面介绍如何使用倍增法在有序的序列中查找满足条件的位置。

题目描述

给定一个单调不降的序列,以及 m m m个查询,每个查询是一个数字 k k k,查找第一个大于等于 k k k的位置。

输入格式

第一行 n n n m m m

第二行 n n n 个元素的序列;

第三行 m m m 个数字,表示 m m m 个查询的 k k k, 每个查询的 k k k,确保在序列的最大值范围内。

输出格式

m m m 个数字,表示第一个大于等于 k k k 的位置,用空格隔开。

样例输入

10 1 
1 2 3 4 6 6 6 8 9 10
6

样例输出

5

数据范围

  • 20%的数据, 1 ≤ n , m ≤ 1000 1\le n,m\le 1000 1n,m1000
  • 100%的数据, 1 ≤ n , m ≤ 1 0 5 1\le n,m\le 10^5 1n,m105 1 ≤ 1\le 1所有元素 ≤ 1 0 9 \le 10^9 109,所有 1 ≤ k ≤ 1\le k \le 1k序列最大值

算法思想

在单调不降的序列中查找一个大于等于 k k k 的位置,朴素的做法是从位置 1 1 1开始判断,不满足要求则每次向右移动 1 1 1个位置,重复进行直到找到满足条件的位置,时间复杂度为 O ( n ) O(n) O(n)

倍增法也从位置 1 1 1开始判断,如果该位置上的数小于 k k k,则将移动的距离增加 1 1 1,然后向右移动;否则,如果该位置上的数大于等于 k k k,则将移动的距离减半,继续判断。重复进行直到不能移动为止,时间复杂度为 O ( l o g n ) O(logn) O(logn)

移动过程如下图所示:
在这里插入图片描述
查找结束后会停留在最后一个小于 k k k的位置上。

代码实现

#include <iostream>
using namespace std;
const int N = 5e5 + 10;
int a[N];
int main()
{
    int n, m, k;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", a + i);
    while(m --) {
        scanf("%d", &k);
        //x表示位置,p表示增加距离
        int x = 0, p = 1;
        while(p != 0) {
        	//x位置上的数小于k,则将移动的距离增加1倍
            if(x + p <= n && a[x + p] < k) {
                x += p;
                p *= 2;
            }
            //x位置上的数大于等于k,则将移动的距离减半
            else p /= 2;
        }
        //x最终停留在最后一个小于k的位置上,应输出x + 1
        printf("%d ", x + 1); 
    }
}

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

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

相关文章

三、C语言中的分支与循环—for循环 (6)

本章分支结构的学习内容如下&#xff1a; 三、C语言中的分支与循环—if语句 (1) 三、C语言中的分支与循环—关系操作符 (2) 三、C语言中的分支与循环—条件操作符 与逻辑操作符(3) 三、C语言中的分支与循环—switch语句&#xff08;4&#xff09;分支结构 完 本章循环结构的…

缓存和数据库,1+1如何大于2?

一、缓存的本质 缓存&#xff0c;简单说就是为了节约对原始资源重复获取的开销&#xff0c;而将结果数据副本存放起来以供获取的方式。 首先&#xff0c;缓存往往针对的是“资源”。我们前面已经多次提到过&#xff0c;当某一个操作是"幂等"的和“安全"的&#…

从传统到现代:知识服务如何被数字化工具重新定义

随着数字技术的快速发展&#xff0c;教育行业正在经历一场前所未有的变革。乔拓云作为知识产品与用户服务的数字化工具&#xff0c;以其卓越的技术实力和创新能力&#xff0c;引领着这场变革。 乔拓云开发的教育系统&#xff0c;为广大知识分享博主提供了一个全新的舞台。这个系…

【springboot实现CURD模版项目-Jesus】

springboot实现CURD模版项目-Jesus STEP 1 项目创建 1.1 新建Spring Initializr项目   1.2 选择需要的依赖 springboot有2.7.2直接选272STEP 2 配置更改 2.1更改maven配置   2.2 检查项目配置jdk、sdk、jre版本一致   2.3 检查pom文件&#xff0c;Maven-Reload project构…

数据库02-06 形式化

01. 03. 04. 05. 06. 07. 08. 09.

【Linux Shell】2. Shell 变量

文章目录 【 1. 变量命名规则 】【 2. 变量的使用 】【 3. 只读变量 】【 4. 删除变量 】【 5. 变量类型 】【 6. Shell 字符串 】6.1 字符串的分类6.2 字符串操作 【 7. Shell 数组 】7.1 定义数组7.2 读取数组7.3 获取数组的长度 【 8. Shell 注释 】8.1 单行注释8.2 多行注释…

『开发工具篇』- 配置 gradle 等相关依赖镜像源

『开发工具篇』- 配置 gradle 等相关依赖镜像源 1.更换gradle下载源2. 配置setting.gradlekts文件gradle文件 1.更换gradle下载源 使用腾讯云的镜像库https://mirrors.cloud.tencent.com/gradle/ gradle-x.x-all.zip&#xff1a;编译后的二进制发布版以及源码和文档gradle-x.…

C++面向对象语法总结(二)

目录 《C面向对象语法总结(一&#xff09;》 十一、继承 继承&#xff0c;可以让子类拥有父类的多有成员&#xff08;变量、函数&#xff09;如下面的代码&#xff1a;Student是子类&#xff08;subclass,派生类&#xff09;&#xff0c;Person是父类&#xff08;superclass…

感恩客户·持续向上-契约锁电子签章

2023年&#xff0c;电子签章成为组织数字化建设中的刚性需求&#xff0c;市场机遇帮助契约锁实现了产品、伙伴、客户、应用场景等全方位的持续发展。 感恩客户和伙伴的支持&#xff0c;让契约锁在2023年不断成长和进步。 感恩客户相伴成长 2023年&#xff0c;契约锁为“政府机关…

【2024.01.03】转行小白-刷css面试题01

总结 1.margin 负值问题 margin-top 和 margin-left 负值&#xff0c;元素向上、向左移动&#xff0c;自己动margin-right 负值&#xff0c;右侧元素左移&#xff0c;自身不受影响&#xff0c;别人动margin-bottom 负值&#xff0c;下方元素上移&#xff0c;自身不受影响 &am…

虾皮跨境电商选品有哪些规则

如何在虾皮&#xff08;Shopee&#xff09;平台上进行跨境电商选品在如今全球化的商业环境中&#xff0c;跨境电商已成为许多卖家拓展业务的重要途径。虾皮&#xff08;Shopee&#xff09;作为一家知名的跨境电商平台&#xff0c;为卖家提供了丰富的销售机会。然而&#xff0c;…

C++八股学习心得.3

1.C 数组 C 支持数组数据结构&#xff0c;它可以存储一个固定大小的相同类型元素的顺序集合。数组是用来存储一系列数据&#xff0c;但它往往被认为是一系列相同类型的变量。所有的数组都是由连续的内存位置组成。最低的地址对应第一个元素&#xff0c;最高的地址对应最后一个…

图像识别原理

图像识别是计算机视觉领域中的一个重要任务&#xff0c;其目标是使计算机系统能够理解和解释图像中的信息。以下是图像识别的基本原理&#xff1a; 1. 数据采集&#xff1a;首先&#xff0c;需要获取图像数据。这可以通过摄像头、传感器、扫描仪等设备来实现。图像可以是静态的…

专访 | STIF2023第四届国际科创节访第七在线CEO赵嘉程

12月15日&#xff0c;在STIF2023第四届国际科创节暨数服会上&#xff0c;第七在线获得年度数智化创新典范奖&#xff0c;第七在线CEO赵嘉程在颁奖典礼现场接受了媒体专访。 主持人&#xff1a;赵总&#xff0c;您好&#xff0c;欢迎您接受我们的专访&#xff0c;首先我们特别想…

业务中台-UAT测试用例示例

今天我来和大家分享一下我们在业务中台UAT测试用例的案例&#xff0c;这个案例的编写方式是参考了其他项目来编写的。这个测试用例主要分为两个部分&#xff1a;用例目录和测试具体内容。 对于UAT测试用例&#xff0c;我们理解应该存在两种不同的编写方式&#xff0c;一种是功…

为自己办一场个展和你的2023告别,上传图片就能生成720云3D线上展厅

来和你的2023告个别吧。只需上传图片并选择一个漂亮的3D展厅&#xff0c;就能生成你的专属展览。在这里&#xff0c;你可以回顾手机里的精彩瞬间&#xff0c;分享你的美好生活或是你的摄影大片、书画作品&#xff0c;也可以是任何值得纪念的瞬间。 通过720云3D空间漫游模板&…

Web前端第9章思维导图

本章内容是关于CSS样式属性&#xff0c;包含CSS单位、CSS字体样式、CSS文本样式、CSS颜色与背景、CSS列表样式、CSS盒模型。重点在于CSS盒模型、CSS文本样式、CSS字体样式。 1. CSS单位 绝对单位 磅&#xff08;pt&#xff09;&#xff0c;pica&#xff08;pc&#xff09;、c…

【EI会议征稿通知】第三届工程管理与信息科学国际学术会议 (EMIS 2024)

第三届工程管理与信息科学国际学术会议 (EMIS 2024) 2024 3rd International Conference on Engineering Management and Information Science 【国际高级别专家出席/新加坡机器人学会支持】 第三届工程管理与信息科学国际学术会议 (EMIS 2024)将于2024年4月12-14日在中国洛…

如何使用LightsOut生成经过混淆处理的DLL

关于LightsOut LightsOut是一款功能强大的DLL生成工具&#xff0c;该工具可以帮助广大研究人员轻松生成经过混淆处理的DLL。该工具专为红队研究人员设计&#xff0c;生成的DLL可以在研究人员尝试绕过反病毒产品时禁用AMSI和ETW&#xff0c;从而更好地测试目标系统的安全性。 …

五步解决Ubuntu界面太小的问题

名人说&#xff1a;莫听穿林打叶声&#xff0c;何妨吟啸且徐行。—— 苏轼《定风波莫听穿林打叶声》 Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#xff09; 对于20版本及以上的unbuntu我们可以通过安装open-vm-tools来解决界面大小的问题&#xff0c;具体步骤如…