【oj刷题】二分查找篇:二分查找算法的原理和应用场景

ops/2024/11/13 9:21:50/

前言:

二分查找算法,又称折半查找算法,是一种在有序数组中查找特定元素的高效查找方法。它通过将搜索区间不断缩小一半,从而在对数时间内找到目标元素。二分查找是基于分治策略的一种典型应用,能够高效的处理许多问题,下面我们就来看一下二分查找算法的原理和应用场景

目录

一、什么是二分查找?

二、二分查找的原理

2.1 朴素二分模板

2.2 查找区间左右端点的模板

三、总结


一、什么是二分查找?

二分查找一般是基于有序数组的,通过比较目标值与中间元素的大小关系,来决定是在数组的左侧还是右侧继续搜索。

我们就拿有序数组来做例子,具体步骤如下:

  1. 初始化:确定查找的起始位置(left)和结束位置(right)。
  2. 循环条件:当left小于等于right时,继续查找。
  3. 查找中间元素:计算mid =left+(right-left)/2,这是当前搜索区间内的中间位置。
  4. 比较与调整
    • 如果中间元素等于目标值,则查找成功,返回中间元素的索引。
    • 如果中间元素小于目标值,则目标值可能在中间元素的右侧,因此将left更新为mid + 1
    • 如果中间元素大于目标值,则目标值可能在中间元素的左侧,因此将right更新为mid - 1
  5. 查找失败:如果循环结束仍未找到目标值,说明目标值不在数组中,返回特定值表示查找失败(通常返回-1或null)。

二、二分查找的原理

二分查找我们可以分为三个模板:

1、朴素的二分模板

2、查找左边界的二分模板

3、查找右边界的二分模板

2.1 朴素二分模板

朴素二分模板我们可以拿下面这题来举个例子:

力扣704 二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1


示例 1:

输入:nums= [-1,0,3,5,9,12],target= 9
输出: 4
解释: 9 出现在nums中并且下标为 4

示例 2:

输入:nums= [-1,0,3,5,9,12],target= 2
输出: -1
解释: 2 不存在nums中因此返回 -1

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

算法原理:

代码实现:

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

2.2 查找区间左右端点的模板

我们也通过一道例题来讲解这个模板:

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

提示:

  • 0 <= nums.length <= 105
  • -10^9 <= nums[i] <= 10^9
  • nums 是一个非递减数组
  • -10^9 <= target <= 10^9

算法原理:

在这道题中我们可以很清楚的看到这道题用朴素二分查找是不能够解决问题的,因为朴素二分查找是用来找一个目标值,但是这道题则是求一个区间范围,所以这里就引出了一个新的模板——查找区间左右断点的模板,下面我们就来看一下这个模板的原理:

1、先来看一下如何找左端点

2、右端点的找法与左端点很相似,最大的区别就是在找中间端点时和移动left和right时有所不同:

代码实现:

vector<int> searchRange(vector<int>& nums, int target) {if (nums.size() == 0)return { -1, -1 }; // 判断数组为空的情况int begin = 0, end = 0;// 1.二分左端点int left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}if (nums[left] != target)return { -1, -1 };elsebegin = left;// 2.二分右端点left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (nums[mid] > target)right = mid - 1;elseleft = mid;}if (nums[right] != target)return { -1, -1 };elseend = right;return { begin, end };
}

上面的就是二分查找的模板,我们平时做题时就可以判断是哪种类型的直接套模板,但是每个题都有各自的细节点,所以写的时候也要注意一下细节

三、总结

以上就是二分查找算法的原理和应用场景,其中讲到的模板是具有通行的,在很多场景下稍作更改就可以使用

感谢各位大佬观看,创作不易,还望各位大佬点赞支持!!!


http://www.ppmy.cn/ops/113108.html

相关文章

Unity实战案例全解析:PVZ 植物卡片状态分析

Siki学院2023的PVZ免费了&#xff0c;学一下也坏 卡片状态 卡片可以有三种状态&#xff1a; 1.阳光足够&#xff0c;&#xff08;且cd好了可以种植&#xff09; 2.阳光不够&#xff0c;&#xff08;cd&#xff1f;好了&#xff1a;没好 &#xff08;三目运算符&#xff09;&…

黑马java学习笔记11(阶段二 第三章3-1~3-2)

以下学习笔记记录于&#xff1a;2024.09.11-2024.09.17 文章目录 阶段二 JavaSE进阶第三章 JDK8新特性3-1 JDK8新特性1&#xff09;Lambda表达式66 认识Lambda表达式67 Lambda表达式的省略规则 2&#xff09;方法引用68 静态方法的引用、实例方法的引用69 特定类型方法的引用70…

门控循环单元(GRU)

困死了。。。 参考视频&#xff1a;56 门控循环单元&#xff08;GRU&#xff09;【动手学深度学习v2】 GRU&#xff1a;门控循环单元&#xff0c;与LSTM类似&#xff0c;解决RNN中不能长期记忆和反向传播中的梯度等问题。但结构比LSTM简单。 关注一个序列&#xff0c;不是每个观…

完整gpt应用(自用)

qrc.py 把gpt_qrc.qrc转化成gpt_qrc.py pyrcc5 -o icons_rc.py icons.qrc <RCC><qresource prefix"img"><file>img/53.png</file><file>img/ai.png</file><file>img/关闭.png</file><file>img/最小化.png&l…

网络安全学习路线,史上最全网络安全学习路线整理

很多小伙伴在网上搜索网络安全时&#xff0c;会出来网络安全工程师这样一个职位&#xff0c;它的范围很广&#xff0c;只要是与网络安全挂钩的技术人员都算网络安全工程师&#xff0c;一些小伙伴就有疑问了&#xff0c;网络安全现在真的很火吗&#xff1f; 那么无涯就带大家看…

PG表空间

目录标题 PG表空间PostgreSQL表空间的最佳实践是什么&#xff1f;如何在PostgreSQL中创建和管理自定义表空间&#xff1f;PostgreSQL表空间对数据库性能的具体影响有哪些&#xff1f;在PostgreSQL中&#xff0c;如何迁移数据到不同的表空间以优化存储布局&#xff1f;PostgreSQ…

IM项目-----语音识别子服务

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、搭建思想二、服务器搭建1.继承speechService类,重写业务代码2.编写语音识别服务器类3.建造者类编写 三.测试 前言 语音转换子服务&#xff0c;用于调用语音…

【深入浅出Redis】Redis常见问题以及解决方案,可用于面试

前面分享了几篇Redis系列文章&#xff0c;那么我们在使用Redis的过程中都会遇到什么问题&#xff1f;如何解决&#xff1f;都有哪些方案&#xff1f; 下面给大家介绍下 redis系列问题以及优化 Redis-hotkey热key 大量请求可能会使redis宕机&#xff0c;继而打到数据库崩溃&am…