算法精讲之【二分】
前言学习二分有两个境界第一个境界是见有序用二分第二个境界是见二段性用二分。有很多人认为二分只能用于有序的情况下其实不然能用二分的前提是具有二段性的特性。下面主要讲解什么是二段性。二段性就是可以将数组的数据分为两个部分这样我们就有mid比较的方式注意我们将mid的值跟谁比较才能确定在哪个区间也是很重要的点也就是寻找与mid比较的基准值最终二分出来的结果就是在这两个区间的极值。二分算法的模板while(left right)//第一个小细节 { mid left (right - left)/2;//第二个小细节 if(nums[mid] target) left mid 1; else right mid;//万恶之源 }跟普通的二分形式上差不多到那时有很多的细节要注意。循环条件不能写等号求中点操作是偏向左边还是偏向右边取决于if else语句中哪两边的操作数不一样就偏向于哪边如果有left mid 1中点就偏向左边如果有right mid - 1就偏向右边左边的操作数和右边的操作数不同时中点就偏向哪一边。class Solution { public: vectorint searchRange(vectorint nums, int target) { int sz nums.size(); vectorint ans(2,-1); if(sz 0) return ans; int left 0, right sz-1; while(left right) { int mid left (right-left)/2; if(nums[mid] target) { left mid 1; } else { right mid; } } if(nums[left] ! target) return ans; ans[0] left; left 0, right sz-1; while(left right) { int mid left (right-left1)/2; if(nums[mid] target) { left mid; } else { right mid-1; } } ans[1] left; return ans; } };因此我们只要发现了二段性直接套公式即可下面精讲二段性如何寻找~例题一34. 在排序数组中查找元素的第一个和最后一个位置本题需要求解查找元素的第一个位置最后一个位置同理因此我们可以将数组分为小于元素和大于等于该元素这两个部分。这里的基准值就是题目中直接给出的target然后用二分算法求解大于等于这个区间的最左端即可~例题二852. 山脉数组的峰顶索引这里的二段性可以分为以峰值为区分点分为两个部分峰值放在左区间和右区间皆可。注意这里的基准值是mid跟前一个值或者和后一个值进行比较方法区分于峰值放在左区间还是右区间。然后根据峰值在哪个区间求解最值即可。例题三162. 寻找峰值注意该题是完全一个无序的状态而我们需要的二段性在一个一个小区间中寻找基准值就是mid坐标和mid前一个值进行比较因为题目默认-1和n位置上的值都是负无穷比较结果进行寻找~例题四寻找旋转排序数组中的最小值-CSDN博客本题的基准值是数组的最后一个元素比较结果可以划分为二段性中的任意一个区间。例题五LCR 173. 点名二分-CSDN博客本题的基准值是数组的下标总结基准值的寻找是不确定的有可能是题目直接给的值也有可能是mid前一个数或者后一个数或者是数组的最后一个元素甚至可以是数组自身的下标

相关新闻

第266篇 ROS2 Navigation2框架概览——模块化导航的标配方案

第266篇 ROS2 Navigation2框架概览——模块化导航的标配方案

SLAM面试高频题聊完了,定位和建图的问题算是有了一个基本的认识。但机器人光知道自己在哪还不够,它还得能从A点走到B点。这就轮到导航框架登场了。 ROS生态里做导航,十年前只有一个move_base。现在到了ROS2时代,Navigation2&…

2026/11/11 20:08:14 阅读更多 →
第267篇 代价地图原理——机器人“眼中“的世界长什么样

第267篇 代价地图原理——机器人“眼中“的世界长什么样

上篇聊了Nav2的整体架构,提到代价地图是导航系统的"眼睛"。规划器再聪明,如果代价地图给的世界是错的,算出来的路径也不可能靠谱。代价地图(Costmap)这个名字听起来挺抽象。说白了就是一张二维网格图&#x…

2026/11/21 2:17:18 阅读更多 →
手握《Android性能优化大厂实战全解析》,迈向调优大神之路不再遥远

手握《Android性能优化大厂实战全解析》,迈向调优大神之路不再遥远

前言性能优化,这一经久不衰的话题,始终伴随着产品的成长与业务的扩展。随着系统能力的逐步逼近瓶颈,性能优化成为了一个我们无法回避的挑战。对于许多一线大厂而言,性能优化不仅是对高级开发者的基本要求,更是他们衡量…

2026/11/14 1:01:13 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/20 23:27:28 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/20 23:27:28 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/20 23:27:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/20 21:55:32 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/20 23:27:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/20 22:59:12 阅读更多 →

日新闻

周新闻

月新闻