二分法中的两个模板

在acwing的算法基础课中,yxc给出了二分的两个模板,这里举有序数组查找某个数的例子来说明这两个模板。

模板1:

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid +1;,计算mid时不需要加1。
此操作用于check条件是获取右半部分的第一个元素。

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

模板2:

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是r = mid - 1或者l =mid;,此时为了防止死循环,计算mid时需要加1。
此操作用于获得左半部分的最后一个元素。

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

在这里插入图片描述
在这里插入图片描述

比如我们有一个有序数组,我们需要找到6的位置,我们可以将数组划分为两个部分,前半部分是小于6的部分,后半部分是大于等于6的部分,那么我们就有两种check的实现方式,分别对应取左半部分的最后一个<=6和取右半部分>=6的第一个:

  1. a[mid]>=6
    此时check函数对应第二部分,即原数组中>=6的部分。
    检查mid是否大于等于6,即我们需要获得第二部分中的第一个元素,其就是最终的答案。
    此时使用第一个模板
#include<iostream>
#include<vector>
using namespace std;

int main(){
	vector<int> a = {1,2,3,4,5,6,7,8,9};
	int l = 0;
	int r = a.size();
	while(l < r){
		int mid = (l + r)>>1;
		if(a[mid] >= 6) r = mid;
		else l = mid + 1;
	}
	cout << l;
	return 0;
} 
  1. a[mid]<=6
    此时check函数对应第一部分,即原数组中<=6的部分。
    检查mid是否小于等于6,即我们需要获得第一部分中的最后一个元素,其就是最终的答案。
    此时使用第二个模板
#include<iostream>
#include<vector>
using namespace std;

int main(){
	vector<int> a = {1,2,3,4,5,6,7,8,9};
	int l = 0;
	int r = a.size();
	while(l < r){
		int mid = (l + r + 1)>>1;
		if(a[mid] <= 6) l = mid;
		else r = mid - 1;
	}
	cout << l;
	return 0;
} 

为什么第二个模板需要l+r+1/2
因为如果r=l+1的时候,不+1的话mid就会等于l,如果进入check条件就会进入死循环。

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

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

相关文章

单链表经典OJ题(三)

目录 1、反转链表 2、合并两个有序链表 3、链表的中间结点 4、环形链表的约瑟夫问题 5、移除链表元素 6、移除元素 1、反转链表 206. 反转链表 - 力扣&#xff08;LeetCode&#xff09; 翻转链表的实质就是更改当前结点的前驱结点和后继结点 假设原链表为:1->2->…

深入理解强化学习——马尔可夫决策过程:随机过程和马尔可夫性质

分类目录&#xff1a;《深入理解强化学习》总目录 下图介绍了强化学习里面智能体与环境之间的交互&#xff0c;智能体得到环境的状态后&#xff0c;它会采取动作&#xff0c;并把这个采取的动作返还给环境。环境得到智能体的动作后&#xff0c;它会进入下一个状态&#xff0c;把…

【电子通识】USB端口颜色编码标识

不知道你有没有发现 USB 口有不同的颜色&#xff0c;黑色、蓝色、紫色、红色、黄色等等&#xff0c;你知道不同颜色的 USB 口各代表什么意思吗&#xff1f; 这些颜色不是USB规范所要求的&#xff0c;设备制造商之间也不一致。例如&#xff0c;Intel使用橙色表示充电端口&#…

Spring Cloud学习(八)【RabbitMQ 服务异步通讯】

文章目录 初识 MQ同步通讯异步通讯MQ 常见框架 RabbitMQ 快速入门RabbitMQ 单机部署RabbitMQ概述常见消息模型 SpringAMQPSimpleQueue 模型WorkQueue 模型发布订阅模型发布订阅-Fanout Exchange发布订阅-DirectExchange发布订阅-TopicExchange消息转换器 初识 MQ 同步通讯 同步…

007 Linux fork()函数

前言 本文将会以提问的形式展开向你介绍fork函数 文章重点 关于fork函数&#xff0c;本文重点在于解决以下疑问 疑问一&#xff1a; 为什么fork之前的代码只有父进程执行&#xff0c;然而fork之后的代码父子进程都要执行 疑问二&#xff1a; 1、既然fork之后父子进程会执行一…

微信小程序:页面跳转传参问题

今天后端大兄弟突然拿着一个反编译过来的小程序源码&#xff0c;问能不能改。我心里直道好家伙&#xff0c;WebGIS开发的岗位&#xff0c;前端的活儿真是一个不少。大致看了看有几处是调整页面和接口修改的&#xff0c;源码部分和Vue项目语法十分相像&#xff0c;就临阵磨枪&am…

【java面试题】Integer对象输出结果是?

/** Copyright (c) 2006, 2023, webrx.cn All rights reserved.**/package cn.webrx;/*** <p>Project: wxbili2mp4 - Test* <p>Powered by webrx On 2023-11-14 20:28:46* <p>描述&#xff1a;<p>** author webrx [webrx126.com]* version 1.0* since …

2.3.5 交换机的VRRP技术

实验2.3.5 交换机的VRRP技术 一、任务描述二、任务分析三、具体要求四、实验拓扑五、任务实施1.交换机的基本配置 六、任务验收七、任务小结 一、任务描述 某公司的网络核心层原来采用一台三层交换机&#xff0c;随着网络应用的日益增多&#xff0c;对网络的可靠性也提出了越来…

生信分析|基因组倍型鉴定

简介 基因组倍型通常指一个生物体细胞中染色体的组合&#xff0c;即染色体数目的倍数。在生物学中&#xff0c;主要有两种类型的基因组倍型&#xff1a;单倍体和多倍体。 「单倍体&#xff08;Haploid&#xff09;&#xff1a;」 单倍体生物体的细胞中只包含每一对同源染色体的…

凸包的学习之路

学习视频选择的是&#xff1a;清华大学邓俊辉教授的《计算几何》课程 关于我为什么学习 凸包&#xff08;Convex Hull&#xff09;&#xff1f; ——在学习过程中遇到了凸包问题&#xff0c;凸包在CV领域的基础性&#xff0c;使我觉得深入了解凸包是必要的。此外&#xff0c;…

交换机基础知识之安全配置

交换机在网络基础设施中扮演着重要角色&#xff0c;它促进了设备之间数据包的流动。正因此&#xff0c;采取适当的安全措施来保护网络免受未经授权的访问和潜在攻击至关重要。本文将全面解读交换机基础安全配置知识&#xff0c;并提供实践方案&#xff0c;以保证安全的网络环境…

【Linux】-再谈动静态库-手把手教你自己制作一个动静态库

&#x1f496;作者&#xff1a;小树苗渴望变成参天大树&#x1f388; &#x1f389;作者宣言&#xff1a;认真写好每一篇博客&#x1f4a4; &#x1f38a;作者gitee:gitee✨ &#x1f49e;作者专栏&#xff1a;C语言,数据结构初阶,Linux,C 动态规划算法&#x1f384; 如 果 你 …

计算机缺失vcruntime140.dll如何修复?超简单的5个解决方法

在我们日常使用电脑的过程中&#xff0c;可能会遇到各种各样的问题和错误提示。其中&#xff0c;一个比较常见的错误提示就是“vcruntime140.dll丢失”。这个错误通常发生在我们尝试运行某个程序或应用时&#xff0c;系统无法找到或加载所需的vcruntime140.dll文件。 vcruntime…

Ubuntu安装mysql(解决ubuntu Access denied for user ‘root‘@‘localhost‘报错)

1、安装mysql sudo apt-get install mysql-server 上述命令会安装以下包&#xff1a; apparmor mysql-client-5.7 mysql-common mysql-server mysql-server-5.7 mysql-server-core-5.7 因此无需再安装mysql-client等。安装过程会提示设置mysql root用户的密码&#xff0c;设…

Java —— 继承

目录 1. 为什么需要继承 2. 继承概念 3. 继承的语法 4. 父类成员访问 4.1 子类中访问父类的成员变量 1. 子类和父类不存在同名成员变量 2. 子类和父类成员变量同名 4.2 子类中访问父类的成员方法 1. 成员方法名字不同 2. 成员方法名字相同 5. super关键字 6. 子类构…

Istio学习笔记-体验istio

参考Istio 入门(三)&#xff1a;体验 Istio、微服务部署、可观测性 - 痴者工良 - 博客园 (cnblogs.com) 在本章中&#xff0c;我们将会学习到如何部署一套微服务、如何使用 Istio 暴露服务到集群外&#xff0c;并且如何使用可观测性组件监测流量和系统指标。 本章教程示例使用…

【JAVA学习笔记】70 - 反射

项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter23/src 反射 一、反射的引出 package com.yinhai.reflection.question;import com.yinhai.Cat;import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IO…

全链路自动化测试

背景 从 SOA 架构到现在大行其道的微服务架构&#xff0c;系统越拆越小&#xff0c;整体架构的复杂度也是直线上升&#xff0c;我们一直老生常谈的微服务架构下的技术难点及解决方案也日渐成熟&#xff08;包括典型的数据一致性&#xff0c;系统调用带来的一致性问题&#xff0…

vue day1(主要是指令)

1、引包 或者&#xff1a;cdn网址 2、创建实例&#xff0c;初始化渲染 3、插值表达式 {{}} 表达式&#xff1a;可以被求值的代码 4、响应式数据&#xff1a;数据发生变化&#xff0c;视图自动更新&#xff08;底层是dom操作&#xff09; data中数据会被添加到实例上&#x…

微信自动添加好友

简要描述&#xff1a; 添加微信好友 请求URL&#xff1a; http://域名地址/addUser 请求方式&#xff1a; POST 请求头Headers&#xff1a; Content-Type&#xff1a;application/jsonAuthorization&#xff1a;login接口返回 参数&#xff1a; 参数名必选类型说明wId…