二分查找系列一-北京尧图网络

前言二分查找属于最恶心细节最多最容易写出死循环的算法。但是同是也是很简单的算法因为有模板而且很容易学会。主要应用与数组有序或者无序(有规律)的情况下。模板主要是朴素二分模板、查找左边界的二分模板、查找右边界的二分模板。1.二分查找题目链接704. 二分查找 - 力扣LeetCode思路图这道题就是一道朴素的二分模板。代码实现class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size()-1; while(left right) { //int mid (right left) / 2; int mid left (right - left 1) / 2; //防溢出 cout left : left - right : right endl; if(nums[mid] target) left mid 1; else if(nums[mid] target) right mid - 1; else return mid; } return -1; } };时空分析时间复杂度时O(logn)底数是2。空间复杂度为O(1)几个变量即可。2.在排序数组中查找第一个和最后一个位置题目链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode思路图这道题相当于是查找左边界和右边界的结合情况还是有点复杂主要细节太多。需要分别分析很容易写出死循环建议每种情况先自己推荐一遍。上图解释了为什么需要有两个中点公式左端点和右端点是不一样的否则就会死循环。代码实现class Solution { public: vectorint searchRange(vectorint nums, int target) { int n nums.size(); if(!n) return {-1,-1}; int left 0, right n - 1, mid 0; vectorint ret; // 查找左端点 while (left right) { // left right 就是结果 mid left (right - left) / 2; if(nums[mid] target) left mid 1; else right mid; } if(nums[left] ! target) return {-1,-1}; ret.push_back(left); //查找右端点 left 0,right n - 1; while(left right) { mid left (right - left 1) / 2; if(nums[mid] target) right mid - 1; else left mid; } ret.push_back(left); return ret; } };时空分析时间复杂度是O(logn)两个二分查找。空间复杂度为O(1)虽然定义了一个vector但是只会消耗两个整型。3.x的平方根题目链接69. x 的平方根 - 力扣LeetCode思路图从1遍历到n使用二分查找注意循环条件和mid的取值公式不是固定的。需具体问题具体分析。只要不会造成死循环即可。像这里中点公式就只能使用另一个否则就会死循环。做多了你就会发现其实就这点套路。循环条件只能是left right当leftright时就是该值应该退出。代码实现class Solution { public: int mySqrt(int x) { if (!x) return x; int left 1,right x; while(left right) { //必须1防止死循环 int mid left (right - left 1) / 2; // cout left : left - right : right endl; if((long)mid*mid x) right mid - 1; else left mid; } return left; } };时空分析时间复杂度为O(logN)一次二分查找。空间复杂度为O(1)。4.搜索插入位置题目链接LCR 068. 搜索插入位置 - 力扣LeetCode思路图循环条件和中点处理需要特判一下别死循环。其他就没什么细节问题了。自己去推演一遍就很清楚了。代码实现class Solution { public: int searchInsert(vectorint nums, int target) { int left 0, right nums.size() - 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 left; else return left 1; } };时空分析时间复杂度为O(logN)一次二分查找完成。空间复杂度为O(1)几个变量即可。5.山脉数组的峰顶索引题目链接852. 山脉数组的峰顶索引 - 力扣LeetCode思路图题目说了一定存在山脉数组所以不用讨论不存在的情况。当二分查找完毕数组应该是一个山顶的形状山顶就是我们要找的结果也就是left right的时候。其次在讨论一下中点公式基本思路就出来了。代码实现class Solution { public: int peakIndexInMountainArray(vectorint arr) { int left 0, right arr.size() - 1; while(left right) { int mid left (right - left) / 2; cout left : left - right : right endl; if(arr[mid] arr[mid1]) right mid; else left mid 1; } return left; } };时空分析时间复杂度为O(logN)一次二分查找即可。空间复杂度为O(1)。

二分查找系列一

相关推荐

Git实战指南：从零开始高效协作开发

基于springboot057洗衣店订单管理系统设计与实现(源码+文档+部署讲解）

结合 Sobel 算子原理，完整详解斜坡宽度缩减锐化算法（Ramp Width Reduction）

更多资讯

Anaconda虚拟环境底层原理与PyCharm配置真相

基于Packet Tracer的校园网设计与配置：VLAN、路由、DHCP与NAT全解析

Jupyter Notebook环境切换：内核注册与常见报错解决

存量电站“零熵增”技改评估：30分钟非侵入式数字化焕新

校园网课程设计从拓扑到排错：VLAN、DHCP与OSPF配置全解析

Python实现租房数据分析和可视化看板全流程实战

今日更新

MATLAB+Yalmip+CPLEX实战：综合能源系统优化调度全流程解析

I3C比I2C快10倍？RK3576实战：速率、DTS配置与混合总线避坑指南

字符串转对象：JSON.parse、new Function与URLSearchParams

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？