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

二分解题的奇技淫巧都有哪些,你还不会吗?

先说一下我为什么要写这篇文章。

“二分“ 查找 or ”二分“ 答案的思想大家想必都知道吧(如果不懂,可以看一下我之前写的一篇文章)。

二分求解

可是呢?思想都会,做题的时候,就懵圈了。

这个题竟然考的是二分吗? 我板子用的对着呢,为什么答案不对呢?我的边界该怎么确定呢?等等。。。

我想大家或多或少都有疑惑吧,那么接下来我谈一谈我对”二分“的理解以及自己的解题技巧。

首先,先引入一个题目【数的范围】。

问题引入

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

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

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

输入格式:

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

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

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

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

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

数据范围:

1 ≤ n ≤ 100000 {1≤n≤100000} 1n100000

1 ≤ q ≤ 10000 {1≤q≤10000} 1q10000

1 ≤ k ≤ 10000 {1≤k≤10000} 1k10000

输入样例:

6 3
1 2 2 3 3 4
3
4
5

输出样例:

3 4
5 5
-1 -1

这道题目是二分的一个经典题目,我们使用二分的板子就可以解决。下面是我的代码。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1e5 + 10;typedef long long LL;
int n, q;
int num[N];int main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin >> n >> q;for (int i = 0; i < n; i ++) cin >> num[i];while(q --) {int target;cin >> target;int l = 0, r = n - 1;while(l < r) {int mid = (l + r) >> 1;if(num[mid] < target) l = mid + 1;else r = mid;}if (num[l] != target) {cout << -1 << " " << -1 << endl;} else {cout << l << " ";r = n - 1;while(l < r) {int mid = (l + r + 1) >> 1;if(num[mid] > target) r = mid - 1;else l = mid;}cout << l << endl;}}return 0;
}

二分重点

以下是“二分”问题的易错点&难点

  • 搜索范围的左右边界如何确定。
    • left = 0 还是 left = -1;
    • right = num.length - 1 还是 right = num.length.
  • 搜索停止的条件。
    • while(left < rigth) 还是 while(left <= right).
  • 中间值能否加入到左/右边界中。
    • right = mid 还是 right = mid - 1;
    • left = mid 还是 left = mid + 1;
  • 中间值 mid 应该如何计算。
    • mid = left + (right - left) / 2 还是 mid = left + (right - left + 1) / 2.

以下重难点的解释,我全用数的范围这道题给大家讲解。

左右边界的确定

情况一

假设我们要寻找大于target的最小值的索引,但是target比原数组num中的所有数据都要大,那么在[0,num.length - 1]的索引范围内就无法找到满足条件的索引,此时就要扩大右边界,也就是令rigth = num.length,此时目标索引就是num.length。而左边界不用动(这里我解释一下,假如target比原数组中的所有数都要小,这个时候大于target的最小值的目标索引就是索引0)。情况一的搜索区间就是[0, num.length]

target = 87
num[] = {12, 17, 45, 56, 66, 68, 69, 72}
right = 0, left = num.length

因为target要比num中的所有元素都要大,所以应该扩大右边界,令rigth = num.length

此时搜索区间为[0, num.length]

情况二

假设我们要寻找小于target的最大值的索引,但是target比原数组num中的所有元素都要小,那么在[0,num.length - 1]的索引范围内就无法找到满足条件的索引,此时就要扩大左边界,也就是令rigth = -1,此时目标索引就是-1。而右边界不用动(这里我解释一下,假如target比原数组中的所有数都要大,这时候小于target的最大值的目标索引就是索引 num.length - 1)。情况二的搜索区间就是[-1, num.length - 1]

target = 9
num[] = {12, 17, 45, 56, 66, 68, 69, 72}
right = 0, left = num.length

因为target要比num中的所有元素都要小,所以应该扩大左边界,令left = -1

此时搜索区间为[-1, num.length - 1]

情况三

假设我们要寻找等于target的索引(一般target都存在),此时搜索区间就是[0, num.length - 1]。如果题目中出现搜索不到的情况,直接返回题目中要求输出的结果即可。

搜索停止条件

情况一

假设在区间[left, right]之间一定有目标索引,那么我们可以令循环截止条件为while(left < right)。当left == right 的时候,目标索引就是left或者rigth

情况二

假设在区间[left, right]之间不一定有目标索引,那么我们可以令循环截止条件为while(left <= right)

中间值的归属

对于中间值的归属问题,我这里举具体的例子给大家讲解。

情况一

假设我们要搜索的是 大于9 的最小值索引,如果 num[mid] <= 9,那么这个 mid 一定不是目标索引,此时应该更新左边界 left = mid + 1;如果 num[mid] > 9,那么此时的 mid 有可能是目标索引,此时应该更新右边界rigth = mid

情况二

假设我们要搜索的是 小于9 的最大值索引,如果 num[mid] >= 9,那么这个 mid 一定不是目标索引,此时应该更新右边界 rigth = mid - 1;如果 num[mid] < 9,那么此时的 mid 有可能是目标索引,此时应该更新左边界left = mid

情况三

假设我们要搜索的是 等于9 的索引,如果 num[mid] > 9,那么这个 mid 一定不是目标索引,此时更新右边界 right = mid - 1;如果 num[mid] < 9,那么这个 mid 也一定不是目标索引,此时更新左边界 right = mid + 1;如果 num[mid] = 9,那么我们就找到正确答案了。

中间值计算

大家可以看到,之前给大家两种计算中间值的公式分别为:

  • 公式一:mid = left + (right - left) / 2,取的是靠近左边的中位数。
  • 公式二:mid = left + (right - left + 1) / 2,取的是靠近右边的中位数。
    这里,我先给大家一个比较好记的技巧如果过程中有令mid = left,就用公式二;否则,就用公式一

接下来说一下为什么要 +1 呢?

假设出现了一种情况left + 1 = right并且mid = left的情况,之后在求 mid的时候,我们使用公式一更新mid,此时mid始终为左边界left,程序就会陷入死循环。所以为了避免这种情况的发生,当出现mid = left的时候,必须使用公式二

而对于,right = mid这个条件则不用担心,对于C++就是向下取整。

总结

对于以上的二分重点介绍,如果按照以上步骤去考虑问题的话,基本上不会出错。

这里,我给出大家,我自己的解题步骤:

  1. 首先审题,判断题目要二分的元素(一般是题目直接要求的答案 or 题目有个固定量,根据固定量而定);
  2. 思考边界该怎么选,是否需要更新左右边界的取值;
  3. 判断在题目的范围内是否一定有答案值,确定循环终止的条件(同时确定check函数的编写);
  4. 暂时使用公式一,如果有mid = left,则更换为公式二

相关文章:

二分解题的奇技淫巧都有哪些,你还不会吗?

先说一下我为什么要写这篇文章。 “二分“ 查找 or ”二分“ 答案的思想大家想必都知道吧&#xff08;如果不懂&#xff0c;可以看一下我之前写的一篇文章&#xff09;。 二分求解 可是呢&#xff1f;思想都会&#xff0c;做题的时候&#xff0c;就懵圈了。 这个题竟然考的是…...

LeetCode-871 最低加油次数

重启力扣每日一题系列&#xff01; 因为过去两个月里掉粉掉的好严重&#xff0c;我想大抵是因为更新的频率不如上半年了&#xff0c;如果我重启了每日一题系列那岂不是至少是每日一更☝&#x1f913;&#xff1f; 也不是每天都更&#xff0c;我有两不更&#xff0c;特难的就不…...

OpenCV-OCR

文章目录 一、OCR技术的基本原理二、OpenCV在OCR识别中的应用1.图像预处理2.文字区域检测3.OCR识别&#xff1a;4.后处理&#xff1a; 三、OCR识别示例代码四、注意事项 OpenCV-OCR主要涉及使用OpenCV库进行光学字符识别&#xff08;OCR&#xff09;的技术。OCR技术可以识别图像…...

Linux卸载mysql

一、查看当前安装mysql情况&#xff0c;查找以前是否装有mysql rpm -qa|grep -i mysql二、停止MySQL服务 三、删除mysql库和文件 查找MySQL库 # 查找命令 find / -name mysql# 显示结果 /var/lib/mysql/var/lib/mysql/mysql/usr/lib64/mysql删除对应的mysql目录 rm -rf /v…...

【大语言模型-论文精读】用于医疗领域摘要任务的大型语言模型评估综述

【大语言模型-论文精读】用于医疗领域摘要任务的大型语言模型评估综述 论文信息&#xff1a; 用于医疗领域摘要任务的大型语言模型评估&#xff1a;一篇叙述性综述&#xff0c; 文章是由 Emma Croxford , Yanjun Gao 博士 , Nicholas Pellegrino , Karen K. Wong 等人近期合作…...

图吧工具箱

图吧工具箱202309绿色版自动解压程序R2.exe&#xff0c;永久有效 链接&#xff1a;https://pan.baidu.com/s/1M6TI7Git8bXOzZX_qZ3LJw?pwdzked 提取码&#xff1a;zked...

vue2 + View design 使用inputNumber设置默认值为undefined但展示数据为1且表单校验不通过的原因

文章目录 一、背景二、操作步骤1.复现前的准备工作&#xff08;1&#xff09;vue版本和view design 版本&#xff08;2&#xff09;创建一个组件&#xff08;组件中根据类型渲染不同的组件&#xff09;&#xff08;3&#xff09;在list.vue页面中引入组件&#xff0c;传入配置&…...

【SpringSecurity】基本流程

【中文文档: Spring Security 中文文档 :: Spring Security Reference】 【英文文档&#xff1a;Spring Security】 以下内容只是记录springsecurity最简单的一种验证流程&#xff0c;所有配置基本都是默认的配置。 引入依赖 <dependency><groupId>org.springf…...

算法-汉诺塔问题(Hanoi tower)

介绍 汉诺塔是源于印度的一个古老传说的小游戏&#xff0c;简单来说就是有三根柱子&#xff0c;开始的时候&#xff0c;第一根柱子上圆盘由大到小&#xff0c;自下往上排列。这个小游戏要实现的目的呢&#xff0c;就是要把第一根柱子上的圆盘移到第三根的柱子上去&#xff1b;…...

HarmonyOS鸿蒙 Next 实现协调布局效果

HarmonyOS鸿蒙 Next 实现协调布局效果 ​ 假期愉快! 最近大A 的涨势实在是红的让人晕头转向&#xff0c;不知道各位收益如何&#xff0c;这会是在路上&#xff0c;还是已经到目的地了? 言归正传&#xff0c;最近有些忙&#xff0c;关于鸿蒙的实践系列有些脱节了&#xff0c;…...

【自然语言处理】(1) --语言转换方法

文章目录 语言转换方法一、统计语言模型1. 词向量转换2. 统计模型问题 二、神经语言模型1. 词向量化2. 维度灾难3. 解决维度灾难4. embedding词嵌入5. Word2Vec技术5.1 连续词袋模型&#xff08;CBOW&#xff09;5.2 跳字模型&#xff08;Skip-gram&#xff09; 总结 语言转换方…...

叉车防撞系统方案,引领安全作业新时代

在现代工业的舞台上&#xff0c;叉车如同忙碌的“搬运工”&#xff0c;在仓储和制造环境中发挥着不可或缺的作用。然而&#xff0c;随着叉车使用频率的不断攀升&#xff0c;安全事故也如影随形&#xff0c;给企业带来经济损失的同时&#xff0c;更严重威胁着操作人员的生命安全…...

Nginx的核心架构和设计原理

Nginx 是一个免费的、开源的、高性能 Http 服务器和反向代理。Nginx 的架构设计是为了提供高性能、稳定性和可扩展性。 Nginx 的主要架构组件和工作原理&#xff1a; 1、Master 进程&#xff1a;Nginx 的运行始于一个 master 进程&#xff0c;它负责管理所有的工作进程。mast…...

leetcode35--搜索插入位置--二分查找刷题

搜索插入位置 一共会出现下面四种情况&#xff1a; 目标值在数组所有元素之前 目标值等于数组中某一个元素 目标值插入数组中的位置 目标值在数组所有元素之后 首先在二分查找的代码之前处理掉目标值在数组所有元素之前和之后的情况如果目标值在数组中的某个位置&#xff0c…...

Django对接支付宝沙箱环境(2024年9月新测有效)

1、申请沙箱环境 #需要填一些个人信息 https://opendocs.alipay.com/ 2、使用支付宝登入&#xff0c;并进入控制台&#xff0c;进入开发者工具推荐-->沙箱 3、获取基本信息 主要是APPID,和支付宝网关地址 4、生成应用私钥和应用公钥和支付宝公钥 上面的接口加签方式选择…...

【MySQL】-- 库的操作

文章目录 1. 查看数据库1.1 语法 2. 创建数据库2.1 语法2.2 示例2.2.1 创建一个名为java114的数据库2.2.2 创建数据库java114&#xff0c;如果数据库不存在则创建2.2.3 查看警告信息 3. 字符集编码和校验&#xff08;排序&#xff09;规则3.1 查看数据库支持的字符集编码3.2 查…...

linux桌面软件(wps)内嵌到主窗口后的关闭问题

程序测试环境是&#xff1a;slackware系统&#xff0c;属于linux系统&#xff0c;有桌面&#xff08;Xface Session&#xff09;。系统镜像是&#xff1a;slackware64-15.0-install-dvd.iso。qt、c代码实现。 问题描述&#xff1a;延续上一篇文章&#xff0c;将wps软件窗口内嵌…...

WindowsTerminal 美化-壁纸随机更换

目录 一. 相关网址二. 壁纸随机更换思路三. 指定 WindowsTermina 壁纸路径四. 编写脚本&#xff0c;随机替换壁纸4.1 powershell脚本4.2 .bat批处理脚本 四. 配置定时任务&#xff0c;添加触发器五. 效果 一. 相关网址 官方下载 Windows Terminal 官方Github微软商店 美化 Oh …...

iOS 多次获取图片主题色不一样

一个需求中&#xff0c;要求获取图片的主题色 代码如下 -(void)kk_getImage:(UIImage *)image fetchthemeColor:(void(^)(UIColor *color))callBack {dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{// 第一步 先把图片缩小 加快计算速度.…...

UE5 武器IK瞄准系统

创建空项目 创建基础蓝图类My_GameMode,My_HUD,My_PlayChar,My_PlayController 项目设置地图模式 近裁平面 0.1 My_PlayChar蓝图中添加摄像机,角色骨骼网格体,武器骨骼网格体 编辑角色骨骼,预览控制器使用特定动画,动画选择ANM_ark-47-Idle hand_r 添加插槽WeaponMes…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

苍穹外卖--缓存菜品

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

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...