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

面试经典150题 -- 二分查找 (总结)

总的链接 : 

面试经典 150 题 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台

二分算法模板 : 

详见 : 

基础二分学习笔记-CSDN博客

35 . 搜索插入位置

链接 :

 . - 力扣(LeetCode)

思路 : 

用二分查找第一个>=target的下标 ;

这里就用最小化查找 , 即可  ;

class Solution {
public:int searchInsert(vector<int>& nums, int target) {// 第一个 >= target 的下标int n = nums.size() ;int l = -1 , r = n ;while(l + 1 < r){// l + 1 == n 结束int mid = l + r >> 1 ;if(nums[mid]>=target) r = mid ;else l = mid ;}// nums[r] ;return r ; }
};

74 . 搜索二维矩阵

链接 : 

. - 力扣(LeetCode)

LC题解链接 : 

. - 力扣(LeetCode)

思路 : 

既然是一个有序表 , 二维矩阵直接当成一维数组做 , 例如下标x 对应二维矩阵中的matrix[x/n][x%n] , 应用最小化二分查找, 找到第一个大于等于target的下标 , 最后判断一下 , 看找到下标的元素值是否为target , 是的话就返回true  , 不是的话 , 返回false ;

代码 : 

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int l = -1 , r = m * n ;while(l+1<r){// 找到第一个 >=target 的下标int mid = (l + r) >> 1 ;int x = matrix[mid/n][mid%n] ;if(x>=target) r = mid ;else l = mid ;}// 右边是可行区域if(r!=m*n && matrix[r/n][r%n] == target) return true ;else return false;}
};

162 . 寻找峰值 : 

链接 : 

. - 力扣(LeetCode)

正解: 

二分 ,

数组可能存在许多个区间峰值 , 但是我们可以用二分找到整个数组的峰值 ;

如果nums[mid] > nums[mid+1] , 那么我们可以使r = mid ;

否则的话 , l = mid + 1 ;

class Solution {
public:int findPeakElement(vector<int>& nums) {int n = nums.size() ;if(n==1) return 0 ;int l = 0 , r = n - 1;while(l < r){int mid = l + r >> 1 ;if(nums[mid] > nums[mid + 1]) r = mid ;else l = mid + 1 ;}return r ;}
};

歪解 : 

直接调用库函数求解  : 

class Solution {
public:int findPeakElement(vector<int>& nums) {return max_element(nums.begin(),nums.end())-nums.begin();}
};

33 . 搜索旋转排序数组

链接

. - 力扣(LeetCode)

思路 : 

将数组从中间分开成左右两部分的时候,一定有一部分的数组是有序的。

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = (left + right) >> 1;if (nums[mid] == target) return mid;if (nums[left] <= nums[mid]) {// left 到 mid 是顺序区间(target >= nums[left] && target < nums[mid]) ? right = mid - 1 : left = mid + 1;}else {// mid 到 right 是顺序区间(target > nums[mid] && target <= nums[right]) ? left = mid + 1 : right = mid - 1;}}return -1;}
};

34. 在排序数组中查找元素的第一个和最后一个位置

链接 : 

. - 力扣(LeetCode)

思路 : 

二分查找 ;

直接套用模板进行二分查找 ;

先找到第一个>=target的元素下标作为左边界, 找到最后一个<=target的下标作为右边界;

最后进行一下边界判断即可 ;

class Solution {
public:int findr(vector<int>& nums, int n ,int target){// 查找最后一个<=target的下标int l = -1 , r = n ;while(l + 1 < r){int mid  = (l + r) >> 1 ;if(nums[mid]<=target) l = mid ;else r = mid ;}return l ;}int findl(vector<int>& nums, int n ,int target){//查找第一个>=target的下标int l = -1 , r = n ;while(l + 1 < r){int mid= (l + r) >>  1;if(nums[mid]>=target) r = mid ;else l = mid ;}return r ;}   vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size() ;if(n==0){return {-1,-1} ;}int l = findl(nums , n , target);int r = findr(nums, n , target);if(l>=0 && l < n && nums[l]==target){return {l,r};}else{return {-1,-1} ;}}
};

153. 寻找旋转排序数组中的最小值

链接 : 

. - 力扣(LeetCode)

思路 : 

首先设置两个指针l, r;先写二分 : 

        // 左边界l,右边界r;

        // 那么最小值一定会在[l,r]这个区间中 ;

        // case 1 : nums[mid] < nums[r] : 说明nums[mid]是最小值右侧元素

        // cese 2 : nums[mid] > nums[r] : 说明nums[mid]是最小值左侧的元素

详细请看代码 : 

代码 : 

class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size() ;int l = 0 , r = n - 1;// 双闭区间// 左边界l,右边界r;// 那么最小值一定会在[l,r]这个区间中 ;// case 1 : nums[mid] < nums[r] : 说明nums[mid]是最小值右侧元素// cese 2 : nums[mid] > nums[r] : 说明nums[mid]是最小值左侧的元素while(l < r){int mid =  (l + r) >> 1  ;if(nums[mid] < nums[r]) r = mid ;else if(nums[mid] > nums[r]) l = mid + 1 ; }return nums[r] ;}
};

相关文章:

面试经典150题 -- 二分查找 (总结)

总的链接 : 面试经典 150 题 - 学习计划 - 力扣&#xff08;LeetCode&#xff09;全球极客挚爱的技术成长平台 二分算法模板 : 详见 : 基础二分学习笔记-CSDN博客 35 . 搜索插入位置 链接 : . - 力扣&#xff08;LeetCode&#xff09; 思路 : 用二分查找第一个>t…...

蓝牙耳机怎么选择比较好?2024年热门机型推荐大揭秘!

​蓝牙耳机已经成为了我们日常生活中不可或缺的一部分&#xff0c;随着技术的发展&#xff0c;人们对蓝牙耳机的要求也在不断提升&#xff0c;不仅希望音质出色&#xff0c;还希望能够在不同的场景下使用。然而&#xff0c;如何挑选一款适合自己的蓝牙耳机却是一门学问。今天&a…...

强制Unity崩溃的两个方法

在Unity中&#xff0c;这两种方法都可以用于强制使应用程序崩溃&#xff0c;但它们的作用略有不同&#xff1a; Application.ForceCrash(0); 这个方法会强制应用程序崩溃&#xff0c;并且参数传入的是一个整数值。当参数为0时&#xff0c;它会导致应用程序崩溃并显示一个“Acce…...

中间件 | Redis - [big-key hot-key]

INDEX 1 big-keyhot-key 1 big-key 分类 字符串型 big-key&#xff1a;字符串最大可以到 512M集合型 big-key&#xff1a;集合个数可以到 2^23 问题 内存空间不均匀指令耗时增加&#xff1a;redis 是单线程的&#xff0c;部分操作的时间复杂度是 O(n) 的&#xff0c;big-ke…...

STM32基础--自己构建库函数

什么是 STM32 函数库 固件库是指“STM32 标准函数库”&#xff0c;它是由 ST 公司针对 STM32 提供的函数接口&#xff0c;即API (Application Program Interface)&#xff0c;开发者可调用这些函数接口来配置 STM32 的寄存器&#xff0c;使开发人员得以脱离最底层的寄存器操作…...

网站被插入虚假恶意链接怎么办?

在当前的电信和网络环境中&#xff0c;诈骗案件频发&#xff0c;许多受害者不幸上当&#xff0c;主要原因是他们点击了诈骗者发送的假链接。这些诈骗网站经常模仿真实网站的外观&#xff0c;使人难以分辨真伪。那么&#xff0c;我们应如何鉴别这些诈骗链接呢&#xff1f; 下面…...

ThreeJs限制模型拖动的范围

之前有讲过ThreeJs中对模型的拖动功能&#xff0c;使用DragControl组件&#xff0c;将模型放到组件的集合中&#xff0c;就可以拖动点击的模型了&#xff0c;这节细化下怎么控制拖动&#xff0c;比如之拖动z轴&#xff0c;或者限制拖动x轴的范围在某个区间&#xff1a; 首先还是…...

关于JVM的小总结(待补充)

JVM组成及他们之间的关系 装载类子系统字节码执行引擎运行时数据区 装载类子系统 类加载器字节码调节器类加载运行时数据区 字节码执行引擎 运行时数据区 线程私有 虚拟机栈本地方法栈程序计数器 线程共享 堆方法区&#xff08;元空间&#xff09;...

day37 贪心算法part6

738. 单调递增的数字 中等 提示 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时&#xff0c;我们称这个整数是单调递增的。 给定一个整数 n &#xff0c;返回 小于或等于 n 的最大数字&#xff0c;且数字呈 单调递增 。 不知道怎么讲思路……以9287举例&#xff0c;…...

38女神节:剧情热梗小游戏新品!预售1折秒杀,手慢无

抖音热剧情热梗小游戏《逆袭大冒险》登录 Cocos Store 预售开启&#xff01;游戏包含 20剧情 40 关卡&#xff0c;先来看下视频吧&#xff01; 游戏内嵌多种小游戏玩法&#xff0c;是不是很有亲切感呢&#xff1f;抽针、流体、重力 3.8女神节特价预售 欢迎加入迷萌游戏《逆袭大…...

岩土工程监测仪器振弦采集仪的发展历程与国内外研究现状

岩土工程监测仪器振弦采集仪的发展历程与国内外研究现状 岩土工程监测仪器河北稳控科技振弦采集仪是用于测量土体或岩石地层的力学性质、地层结构、地下水位等参数的一种仪器设备。它通过振动在地下传播的声波信号的传播速度和特性&#xff0c;来推断地层的物理性质。以下是对…...

Git 掌握

目录 一、前言 二、centos安装Git 三、Git基本操作 (1) 创建Git本地仓库 (2) 配置Git (3) 认识工作区&#xff0c;暂存区&#xff0c;版本库 四、添加文件 五、查看.git文件 六、修改文件 七、版本回退 八、撤销修改 (1) 场景一 对于还没有add的代码 (2) 场景二 已…...

面试题之——事务失效的八大情况

事务失效的八大情况 一、非public修饰的方法 Transactional注解只能在在public修饰的方法下使用。 /*** 私有方法上的注解&#xff0c;不生效&#xff08;因私有方法Spring扫描不到该方法&#xff0c;所以无法生成代理&#xff09;*/ Transactional private boolean test() …...

一些硬件知识(六)

防反接设计&#xff1a; 同步电路和异步电路的区别: 同步电路:存储电路中所有触发器的时钟输入端都接同一个时钟脉冲源&#xff0c;因而所有触发器的状态的变化都与所加的时钟脉冲信号同步。 异步电路:电路没有统一的时钟&#xff0c;有些触发器的时钟输入端与时钟脉冲源相连…...

前端React篇之哪些方法会触发 React 重新渲染?重新渲染 render 会做些什么?

目录 哪些方法会触发 React 重新渲染&#xff1f;重新渲染 render 会做些什么&#xff1f;setState()案例需求总结 forceUpdate()案例需求总结 props改变案例需求总结 context改变案例需求总结 哪些方法会触发 React 重新渲染&#xff1f;重新渲染 render 会做些什么&#xff1…...

PHP伪协议是什么?

PHP伪协议是一种特殊的URL协议&#xff0c;它允许PHP直接从PHP内部生成数据或者访问PHP自身处理的数据流&#xff0c;而不需要外部资源。这些协议是由PHP解释器内部定义和处理的&#xff0c;不同于HTTP、FTP、HTTPS等标准网络协议。下面是PHP伪协议的说明&#xff1a; 1. file…...

npm使用

要查看当前 npm 使用的镜像源地址&#xff0c;你可以使用以下命令&#xff1a; npm get registry这个命令会输出当前 npm 配置的镜像源地址。如果你想查看所有可用的镜像源列表&#xff0c;可以使用 nrm 这个工具&#xff0c;它是一个 npm 源管理器&#xff0c;可以帮助你查看…...

美国国家安全局(NSA)和美国政府将Delphi/Object Pascal列为推荐政府机构和企业使用的内存安全编程语言

上周&#xff0c;美国政府发布了《回到构建块&#xff1a;通往安全和可衡量软件的道路》的报告。本报告是美国网络安全战略的一部分&#xff0c;重点关注多个领域&#xff0c;包括内存安全漏洞和质量指标。 许多在线杂志都对这份报告发表了评论&#xff0c;这些杂志强调了对 C…...

C++中的内部类

一、内部类的概念 如果一个类定义在另一个类的内部&#xff0c;那么这个类就叫做内部类。&#xff08;内部类其实和一个独立的类没有区别&#xff0c;只是它会受到外部类访问限定符以及类域的限制&#xff0c;且是外部类的友元&#xff09; 如果B类是A类的内部类&#xff0c;…...

华为“仓颉”不是中文编程:中文编程早有所属,势如破竹

“何时能见证中国自主研发的编程语言崛起&#xff1f;”这是我们这些对IT生态心怀关切的人常常深思的问题。 语言&#xff0c;作为文化的灵魂&#xff0c;总是与特定的环境和人群紧密相连。无论是中文还是英语&#xff0c;它们都不仅仅是交流的工具&#xff0c;更是各自文化背…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

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

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

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...

更新 Docker 容器中的某一个文件

&#x1f504; 如何更新 Docker 容器中的某一个文件 以下是几种在 Docker 中更新单个文件的常用方法&#xff0c;适用于不同场景。 ✅ 方法一&#xff1a;使用 docker cp 拷贝文件到容器中&#xff08;最简单&#xff09; &#x1f9f0; 命令格式&#xff1a; docker cp <…...