二分查找算法:穿越算法迷宫的指南

2024-06-12 00:44

本文主要是介绍二分查找算法:穿越算法迷宫的指南,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

✨✨✨学习的道路很枯燥,希望我们能并肩走下来!

目录

前言

一.  二分查找算法介绍

二 二分查找的题目解析

2.1 二分查找

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

2.3 搜索插入位置 

2.4 x的平方根 

 2.5 山峰数组峰顶的索引

 2.6 寻找峰值

2.7 寻找旋转数组中的最小值 

2.8 点名 

 三. 二分算法总结+模板

总结


前言

本篇详细介绍了二分查找算法的使用,让使用者了解二分查找,而不是仅仅停留在表面, 文章可能出现错误,如有请在评论区指正,让我们一起交流,共同进步!


一.  二分查找算法介绍

二. 二分查找的题目解析

开始之前可以去总结部分被去看看模板,再结合题目理解

2.1 二分查找

704. 二分查找 - 力扣(LeetCode)

 思路:(模版1)正常的二分查找策略

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

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

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

思路:找第一个,用左区间端点查找(模版2),找最后一个,用右端点区间查找(模版3) 

 

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {//处理边界情况if(nums.size() == 0) return {-1,-1};int left = 0;int right = nums.size()-1;int first = 0;//  1.二分左端点while(left<right)  //先找第一次的{int mid = (right - left)/2+left;if(nums[mid] >= target){right = mid;}else{left = mid +1;}}//判断是否有结果if(nums[left] != target) return {-1,-1};else first = left;  //标记一下左端点//  2.二分右端点left = 0,right = nums.size()-1;while(left<right){int mid = (right - left+1)/2+left;if(nums[mid] <= target){left = mid;}else{right = mid -1;}}return {first,right};}
};

2.3 搜索插入位置 

35. 搜索插入位置 - 力扣(LeetCode) 

 思路:左端区间查找 (右区间查找也行

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size()-1;if(nums[right]<target) return right + 1;while(left < right){int mid = (right - left)/2 + left;if(nums[mid]>=target) right = mid;else left = mid + 1;}return left;}
};

2.4 x的平方根 

69. x 的平方根 - 力扣(LeetCode) 

思路:右端区间二分查找法 

class Solution {
public:int mySqrt(int x) {if(x == 0) return 0; //处理边界情况int left = 1, right = x;while(left<right){long long mid = (right - left + 1) /2+left; //防溢出if(mid*mid<=x) left = mid;else right = mid - 1;}return left;}
};

 2.5 山峰数组峰顶的索引

852. 山脉数组的峰顶索引 - 力扣(LeetCode) 

思路:左或右端区间查找

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1 ,right = arr.size()- 2;while(left < right){int mid = (right - left + 1) / 2 + left;if(arr[mid]>arr[mid-1]) left = mid;else right = mid - 1;}return left;}
};

 2.6 寻找峰值

162. 寻找峰值 - 力扣(LeetCode) 

 思路:左或右端点区间查找

 右区间:

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

2.7 寻找旋转数组中的最小值 

153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)

思路:左区间端点查找法 

class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size()-1;int n = nums.size();while(left<right){int mid = (right - left)/2+left;if(nums[mid]>nums[n-1]) left = mid + 1;else right = mid;}return nums[left];}
};

2.8 点名 

LCR 173. 点名 - 力扣(LeetCode)

 思路:左区间查找

class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0, right = records.size()-1;while(left<right){int mid = (right - left)/2+left;if(records[mid] == mid) left = mid + 1;else right = mid;}//处理细节问题:最后一个位置缺少return records[left] == left ? left+1 : left;}
};

 三. 二分算法总结+模板

二分查找的策略基本上都是去找一个数,对应的有三种模版:正常的二分查找、左区间端点查找、右区间端点查找。其中正常的二分查找局限性比较大,必须得是升序且限制条件较多,大多数情况下不符合题意。最常用的就是左区间端点(关键是left会大跳跃,且目标位置在较大值区间的左边)和右区间端点法(关键是right会大跳跃,且目标位置在较小值区间的右边)。 

图from:算法思想总结:二分查找算法-CSDN博客 


总结

✨✨✨各位读友,本篇分享到内容是否更好的让你理解二分查找算法,如果对你有帮助给个👍赞鼓励一下吧!!
🎉🎉🎉世上没有绝望的处境,只有对处境绝望的人。
感谢每一位一起走到这的伙伴,我们可以一起交流进步!!!一起加油吧!!

这篇关于二分查找算法:穿越算法迷宫的指南的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1052720

相关文章

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Java使用Mail构建邮件功能的完整指南

《Java使用Mail构建邮件功能的完整指南》JavaMailAPI是一个功能强大的工具,它可以帮助开发者轻松实现邮件的发送与接收功能,本文将介绍如何使用JavaMail发送和接收邮件,希望对大家有所... 目录1、简述2、主要特点3、发送样例3.1 发送纯文本邮件3.2 发送 html 邮件3.3 发送带

IDEA连接达梦数据库的详细配置指南

《IDEA连接达梦数据库的详细配置指南》达梦数据库(DMDatabase)作为国产关系型数据库的代表,广泛应用于企业级系统开发,本文将详细介绍如何在IntelliJIDEA中配置并连接达梦数据库,助力... 目录准备工作1. 下载达梦JDBC驱动配置步骤1. 将驱动添加到IDEA2. 创建数据库连接连接参数

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

Java中使用注解校验手机号格式的详细指南

《Java中使用注解校验手机号格式的详细指南》在现代的Web应用开发中,数据校验是一个非常重要的环节,本文将详细介绍如何在Java中使用注解对手机号格式进行校验,感兴趣的小伙伴可以了解下... 目录1. 引言2. 数据校验的重要性3. Java中的数据校验框架4. 使用注解校验手机号格式4.1 @NotBl

使用Java发送邮件到QQ邮箱的完整指南

《使用Java发送邮件到QQ邮箱的完整指南》在现代软件开发中,邮件发送功能是一个常见的需求,无论是用户注册验证、密码重置,还是系统通知,邮件都是一种重要的通信方式,本文将详细介绍如何使用Java编写程... 目录引言1. 准备工作1.1 获取QQ邮箱的SMTP授权码1.2 添加JavaMail依赖2. 实现

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1