二分查找模版

对于一个递增序列我们要找大于等于target的数,返回结果的下标时
比如 序列 5 7 7 8 8 10
初始化左右指针l=0 r=n-1 猜测区间 [l,r] 闭区间,mid=(l+r)/2 防溢出就写成 mid=l+(r-l)/2
如果有nums[mid]<target 那么[l,mid]这个区间的数就都小于target 更新 l=mid+1;
否则就是nums[mid]>=target [mid,r]这个区间的数都大于等于target 更新r=mid-1;
终止时返回l,拿这个案例序列走一遍找8,最后l和r都指向下标3处的8,此时,l=3,r=3,mid=3 然后更新r=mid-1=2 l>r 跳出循环 结果就是l或 r+1 返回3,再比如找3,会发现r不断更新r=1,-1 跳出循环
返回l=0, 当找大于10的数时,l不断更新r不动了最后跳出循环就是返回数组的长度

int lower_bound1(vector<int>&nums,int target)
{int l=0,r=nums.size()-1;  //闭区间[l,r]while(l<=r){int mid=l+(r-l)/2//防溢出if(nums[mid]<target)l=mid+1;else r=mid-1;}return l;     //最后跳出循环 l>r    结果是r+1 或者l 因为 此时r+1=l
}
int lower_bound2(vector<int>&nums,int target)
{int l=0,r=nums.size();    // 左闭右开  [l,r)while(l<r){int mid=l+(r-l)/2;if(nums[mid]<target)l=mid+1;elseright=mid;}return l  //或者return r
}
int lower_bound3(vector<int>&nums,int target)
{int l=-1,r=nums.size() ;     //  开区间 (l,r)while(l+1<r){int mid=l+(r-l)/2;if(nums[mid]<target)l=mid;elser=mid;}return r;
}

上述我们讨论了 在序列中找 >=target 的计算方法 ,对于>target <target <=target 这里都可以从第一种情况来转换:
我们要找大于target的数,就可以使用上面的lower_bound 找 >=target+1
我们要找小于target的数 就可以使用上面的lower_bound招到>=target 的数左边的那个数,也就是返回的下标再减一
我们找小于等于target的数 就可以使用前面大于target返回的结果减一

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

计算机网络 第二章物理层

计算机网络第二章知识点速刷 其中重要的是信源和信宿&#xff0c;以及调制解调器在通信模型当中起到的作用。 单工、半双工和全双工。

【Java 进阶篇】JDBC 数据库连接池详解

数据库连接池是数据库连接的管理和复用工具&#xff0c;它可以有效地降低数据库连接和断开连接的开销&#xff0c;提高了数据库访问的性能和效率。在 Java 中&#xff0c;JDBC 数据库连接池是一个常见的实现方式&#xff0c;本文将详细介绍 JDBC 数据库连接池的使用和原理。 1…

计组——I/O方式

一、程序查询方式 CPU不断轮询检查I/O控制器中“状态寄存器”&#xff0c;检测到状态为“已完成”之后&#xff0c;再从数据寄存器取出输入数据。 过程&#xff1a; 1.CPU执行初始化程序&#xff0c;并预置传送参数&#xff1b;设置计数器、设置数据首地址。 2. 向I/O接口发…

腾讯云服务器选购指南:如何选择一台合适的云服务器配置?

腾讯云服务器配置如何选择&#xff1f;CPU内存、带宽和系统盘怎么选择合适&#xff1f;个人用户可以选择轻量应用服务器&#xff0c;企业用户可以选择云服务器CVM&#xff0c;2核2G3M带宽轻量服务器95元一年、2核4G5M服务器168元一年&#xff0c;企业用户可以选择标准型S5云服务…

1300*C. Rumor(并查集贪心)

解析&#xff1a; 并查集&#xff0c;求每个集合的最小费用。 每次合并集合的时候&#xff0c;根节点保存当前集合最小的费用。 #include<bits/stdc.h> using namespace std; #define int long long const int N1e55; int n,m,a[N],p[N],cnt[N]; int find(int x){retur…

分布式锁:四种方案解决商品超卖的方案

一 分布式锁 1.1 分布式锁的作用 在多线程高并发场景下&#xff0c;为了保证资源的线程安全问题&#xff0c;jdk为我们提供了synchronized关键字和ReentrantLock可重入锁&#xff0c;但是它们只能保证一个工程内的线程安全。在分布式集群、微服务、云原生横行的当下&#xff…

深度学习笔记_4、CNN卷积神经网络+全连接神经网络解决MNIST数据

1、首先&#xff0c;导入所需的库和模块&#xff0c;包括NumPy、PyTorch、MNIST数据集、数据处理工具、模型层、优化器、损失函数、混淆矩阵、绘图工具以及数据处理工具。 import numpy as np import torch from torchvision.datasets import mnist import torchvision.transf…

uniapp 实现下拉筛选框 二次开发定制

前言 最近又收到了一个需求&#xff0c;需要在uniapp 小程序上做一个下拉筛选框&#xff0c;然后找了一下插件市场&#xff0c;确实有找到&#xff0c;但不过他不支持搜索&#xff0c;于是乎&#xff0c;我就自动动手&#xff0c;进行了二开定制&#xff0c;站在巨人的肩膀上&…

归并排序及其非递归实现

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 目录 归并排序递归实现 归并排序非递归实现 归并排序递归实现 图示&#xff1a; 代码&#xff1a; 先分再归并&#xff0c;像是后序一般。 //归并排序 void MergeSort(int* arr, int left, int right) {int* temp (int…

tcp滑动窗口原理

18.1 滑动窗口 我们再来看这个比喻&#xff1a; 网络仅仅是保证了整个网络的连通性&#xff0c;我们我们基于整个网络去传输&#xff0c;那么是不是我想发送多少数据就发送多少数据呢&#xff1f;如果是这样的话&#xff0c;是不是就会像我们的从一个池塘抽水去灌到另外一个…

速看:免费领取4台阿里云服务器_申请入口及领取流程

注册阿里云账号&#xff0c;免费领云服务器&#xff0c;最高领取4台云服务器&#xff0c;每月750小时&#xff0c;3个月免费试用时长&#xff0c;可快速搭建网站/小程序&#xff0c;部署开发环境&#xff0c;开发多种企业应用。阿里云服务器网分享阿里云服务器免费领取入口、免…

openGauss学习笔记-89 openGauss 数据库管理-内存优化表MOT管理-内存表特性-使用MOT-MOT使用查询原生编译

文章目录 openGauss学习笔记-89 openGauss 数据库管理-内存优化表MOT管理-内存表特性-使用MOT-MOT使用查询原生编译89.1 查询编译&#xff1a;PREPARE语句89.2 运行命令89.3 轻量执行支持的查询89.4 轻量执行不支持的查询89.5 JIT存储过程89.6 MOT JIT诊断89.6.1 mot_jit_detai…

Pygame中监控鼠标动作的方法

在Pygame中监控键盘按键的方法_pygame获取键盘输入-CSDN博客中提到&#xff0c;通过在while True循环中获取队列中事件的方法监控键盘动作。监控鼠标动作的方法与监控键盘动作的方法相同。 相关连接1 队列与事件的相关知识&#xff0c;请参考 Pygame中监控键盘按键的方法_pyg…

网络爬虫--伪装浏览器

从用户请求的Headers反反爬 在访问某些网站的时候&#xff0c;网站通常会用判断访问是否带有头文件来鉴别该访问是否为爬虫&#xff0c;用来作为反爬取的一种策略。很多网站都会对Headers的User-Agent进行检测&#xff0c;还有一部分网站会对Referer进行检测&#xff08;一些资…

电脑通过串口助手和51单片机串口通讯

今天有时间把电脑和51单片机之间的串口通讯搞定了&#xff0c;电脑发送的串口数据&#xff0c;单片机能够正常接收并显示到oled屏幕上&#xff0c;特此记录一下&#xff0c;防止后面自己忘记了怎么搞得了。 先来两个图片看看结果吧&#xff01; 下面是串口3.c的文件全部内容&a…

Eureka

大家好我是苏麟今天带来Eureka的使用 . 提供者和消费者 在服务调用关系中&#xff0c;会有两个不同的角色&#xff1a; 服务提供者&#xff1a;一次业务中&#xff0c;被其它微服务调用的服务。&#xff08;提供接口给其它微服务&#xff09; 服务消费者&#xff1a;一次业务…

微信小程序点单左右联动的效果实现

微信小程序点单左右联动的效果实现 原理解析&#xff1a;   点击左边标签会跳到右边相应位置&#xff1a;点击改变rightCur值&#xff0c;转跳相应位置滑动右边&#xff0c;左边标签会跳到相应的位置&#xff1a;监听并且设置每个右边元素的top和bottom&#xff0c;再判断当…

计算机网络基础(一):网络系统概述、OSI七层模型、TCP/IP协议及数据传输

通信&#xff0c;在古代是通过书信与他人互通信息的意思。 今天&#xff0c;“通信”这个词的外沿已经得到了极大扩展&#xff0c;它目前的大意是指双方或多方借助某种媒介实现信息互通的行为。 如果按照当代汉语的方式理解“通信”&#xff0c;那么古代的互遣使节、飞鸽传书…

竞赛选题 机器视觉的试卷批改系统 - opencv python 视觉识别

文章目录 0 简介1 项目背景2 项目目的3 系统设计3.1 目标对象3.2 系统架构3.3 软件设计方案 4 图像预处理4.1 灰度二值化4.2 形态学处理4.3 算式提取4.4 倾斜校正4.5 字符分割 5 字符识别5.1 支持向量机原理5.2 基于SVM的字符识别5.3 SVM算法实现 6 算法测试7 系统实现8 最后 0…

Windows安装Docker并创建Ubuntu环境及运行神经网络模型

目录 前言在Windows上安装Docker在Docker上创建Ubuntu镜像并运行容器创建Ubuntu镜像配置容器&#xff0c;使其可以在宿主机上显示GUI 创建容器并运行神经网络模型创建容器随便找一个神经网络模型试试 总结 前言 学生党一般用个人电脑玩神经网络&#xff0c;估计很少有自己的服…