二分查找算法:朴素二分+左右边界二分力扣实战应用

2024-08-26 05:44

本文主要是介绍二分查找算法:朴素二分+左右边界二分力扣实战应用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录:

1、二分查找算法简介

2、算法原理及时间复杂度分析

2.1 朴素二分算法

3.2 查找左右边界的二分算法

3.2.1 查找左边界

3.2.2 查找右边界

3.3 时间复杂度分析

3、二分查找算法模版

3.1 朴素二分模版

3.2 查找左右边界的二分模版

4、算法应用【leetcode】

4.1 题一:搜素插入位置

4.1.1 思路分析

4.1.2 算法代码

4.2 题二:x的平方根

4.2.1 思路分析

4.2.2 算法代码

4.3 题三:山峰数组的峰顶索引

4.3.1 思路分析

4.3.2 算法代码

4.4 题四:寻找峰值

4.4.1 思路分析

4.4.2 算法代码

4.5 题五:寻找旋转排序数组中的最小值

4.5.1 思路分析

4.5.2 算法代码

4.6 题六:点名 (原:剑指Offer:0~n-1 中缺失的数字 )

 4.6.1 思路分析

4.6.2 算法代码


1、二分查找算法简介

算法,是一种思想,并不是固定的模式,我们可以使用一种算法思想解决多种问题。

二分查找算法,是一个细节最多、最恶心、最容易写出死循环的一个算法,但是当我们熟练掌握后它就可以变成一个最简单的算法,利用它,仅仅使用十几行代码就可以解决掉一个难题,所以在算法学习的路途中,二分查找算法的学习是极为重要且必不可少的。

二分法查找算法的使用条件:数据具有“二段性”。(并非数据有序)

注意:并不是只有数据有序的情况下才可以使用二分查找算法,只要数据具有二段性,即使数据乱序,也可以使用二分查找算法!!!

2、算法原理及时间复杂度分析

这里通过例题为大家讲解算法原理。

2.1 朴素二分算法

. - 力扣(LeetCode)

使用二分查找算法的关键点是:数据具有“二段性”。

因为数组为升序排列,所以target左边的数据均<target,target右边的数据均>target,故可将数据分为“二段”,具有二段性,可以使用二分查找算法。

定义left和right指针分别指向数组0下标处和nums.length-1处,以及定义他们的中间位置mid,将nums[mid]和target比较,

  1. nums[mid] < target ---> left = mid+1;
  2. nums[mid] > target ---> right = mid-1;
  3. nums[mid] == target ---> 返回结果;

这样一次比较即可过滤掉一半数据,大大提高了查找效率。、

注意:

  • 循环条件为:left <= right
  • 为防止数据溢出,更新mid的方式为:mid = left + (right - left) / 2;或者mid = left + (right - left + 1) / 2;

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

注意:朴素二分算法因为太过简单,所以基本不会考察,重点是下方的边界二分查找算法的思想。


3.2 查找左右边界的二分算法

. - 力扣(LeetCode)

因为数组为非递减排序,也就是说数据要么相等,要么递增,而我们要找的就是相等数据target的开始和结束位置。

也就是说,我们要找到target的左边界位置和右边界位置,而target的左边的数据小于target,右边的数据大于target,数据同样具有二段性,可以使用二分查找算法。

同样定义left和right指针,定义mid指向他们的中间位置。

3.2.1 查找左边界

  1. 循环条件为:left < right,left == right时就是最终结果,结束循环
  2. nums[mid] < target ---> left = mid+1;//mid的位置肯定不为左边界,所以left = mid+1
  3. num[mid] >= target ---> right = mid;//mid的位置可能就是左边界,所以right=mid
  4. 更新mid:mid = left + (right - left) / 2;

3.2.2 查找右边界

  1. 循环条件为:left < right,left == right时就是最终结果,结束循环
  2. nums[mid] <= target ---> left = mid;//mid的位置可能就是右边界,所以left=mid
  3. nums[mid] > target ---> right = mid-1;//mid的位置肯定不为右边界,所以right= mid-1
  4. 更新mid:mid = left + (right - left + 1) / 2;因为更新right或left时,有-1操作,所以这里更新mid要+1(技巧,记忆即可)

class Solution {public int[] searchRange(int[] nums, int target) {int left = 0;int right = nums.length - 1;int[] arr = new int[]{-1,-1};//nums为空数组if (nums.length == 0) return arr;//查找左边界while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;}else {right = mid;}}//数组中不存在targetif (nums[left] != target) return arr;arr[0] = left;left = 0;right = nums.length - 1;//查找右边界while (left < right) {int mid = left + (right - left + 1) / 2;if (nums[mid] <= target) {left = mid;}else {right = mid - 1;}}arr[1] = left;return arr;}
}

注意:

  • 朴素二分算法的循环条件是:left <= right;因为要查找的数据可能就在left和right重叠的位置处。
  • 边界二分算法的循环条件是:left < right;因为当left == right时,就是最终结果。
  • 为避免数据溢出:mid = left + (right - left) / 2 或者 mid = left + (right - left + 1) / 2,朴素算法+1与否都可以,但是在找边界的二分算法中,若更新left或者right时,有-1出现,则更新的mid要+1。

3.3 时间复杂度分析

第一次二分查找剩下n/2个数据,第二次二分查找剩下n/4个数据,第三次二分查找升序n/8个数据,直至最后一次(第x次)二分查找剩下1个数据(此时查找成功),则n/2^{x} == 1,计算得x == logN,因为x就是循环执行的次数,故二分查找算法时间复杂度为:O(logN)

大家可能觉得O(logN)对于O(N)的提升不是很大,其实并不是这样,举个例子:

假设存储了2^{32}个数据,若用O(N)的算法去查找某一个数据,即遍历所有数据,那么最多需要查找2^{32}=4,294,967,296次;而使用O(logN)的算法,则最多查找32次就可以查找成功。

综上所述,O(logN)相对于O(N)的提升非常的大,故二分查找算法是一个极为高效的算法,每次都能排除掉一半的数据,从而快速定位到目标位置。

3、二分查找算法模版

对于算法的模版,一定不要死记硬背,要理解后再记忆,这样才可以在不同的题目中灵活使用该算法。

3.1 朴素二分模版

朴素二分模版是最简单的二分模版,因为简单,所以也很少考察。

注意:朴素模版中的循环条件为: left <= right

//朴素二分模版while (left <= right) {int mid = left + (right - left) / 2;//避免数据溢出//int mid = left + (right - left + 1) / 2;在朴素二分中,加不加1均可if(....) {left = mid+1;} else if (....) {right = mid-1;}else {return ....;}}

3.2 查找左右边界的二分模版

注意:边界模版中的循环条件为: left < right


4、算法应用【leetcode】

4.1 题一:搜素插入位置

. - 力扣(LeetCode)

4.1.1 思路分析

分析数据,可以发现target要插入的位置就是第一个比target大的数据的位置,而这个位置左侧的均小于target,右侧的数据均大于target,故具有二段性,可以使用二分查找算法。

而我们的目的就是:找到第一个大于target的数据的位置,返回这个位置的下标即可。

需要注意一个边界情况:当target比所以数据都大时,也就是说target要插入数组的末尾,需要特殊处理。

4.1.2 算法代码

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

4.2 题二:x的平方根

. - 力扣(LeetCode)

4.2.1 思路分析

分析数据,因为目标数据的平方是 小于或等于 x的,所以目标数据及其左侧数据(包括目标数据)的平方均小于等于x,右侧数据的平方均大于x。故具有二段性,可使用二分查找算法解决该题。

4.2.2 算法代码

class Solution {public int mySqrt(int x) {long left = 0;long right = x;while (left < right) {//mid*mid 可能超出范围,定义为long长整型long mid = left + (right - left + 1) / 2;if (mid * mid <= x) {left = mid;}else {right = mid - 1;}}return (int)left;}
}

4.3 题三:山峰数组的峰顶索引

. - 力扣(LeetCode)

4.3.1 思路分析

由题意可知,数组一定为山峰,故峰顶左侧的数据一定小于峰顶值,峰顶右侧的数据一定大于峰顶值,故数据具有二段性,可使用二分查找算法。且题目已说明使用O(logN)的算法,故必须使用二分查找算法。

算法思想很简单:

  1. 若arr[mid] > arr[mid-1],则峰顶一定在mid右侧或峰顶就为mid;//left = mid
  2. 若arr[mid] < arr[mid-1],则峰顶一定在mid左侧;//right = mid-1

4.3.2 算法代码

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

4.4 题四:寻找峰值

. - 力扣(LeetCode)

4.4.1 思路分析

该题思路与上一题山峰数组的解题思路是一模一样的,只不过可能存在多个山峰,也就是说数组是完全无序的,所以,二分查找算法的使用并不局限于有序数组,只要数据具有二段性,就可以使用二分查找算法。

  1. 将中间值arr[mid]与arr[mid-1]比较,若arr[mid] < arr[mid-1],说明在左侧一定有峰值,而右侧是不确定的,可能有也可能没有,这样就可以过滤掉右侧数据,在左侧数据继续寻找山峰;
  2. 同样,若arr[mid] > arr[mid-1],说明右侧一定有山峰,而左侧不确定,过滤左侧数据,故发现数据具有二段性,能够使用二分查找算法。
  3. 因为 nums[-1] = nums[n] = -∞,所以即使数组为递增或递减序列时,也能够正确查找到峰值的位置。

4.4.2 算法代码

class Solution {public int findPeakElement(int[] arr) {int left = 0;int right = arr.length - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if(arr[mid] > arr[mid - 1]) {left = mid;}else {right = mid - 1;}}return left;}
}

4.5 题五:寻找旋转排序数组中的最小值

. - 力扣(LeetCode)

4.5.1 思路分析

因为数组原来是升序排列,所以经过旋转,数值大的元素就移动到了数组的前面部分。

所以:

  1. 未经过旋转的元素必然小于等于数组的最后一个元素。
  2. 而经过旋转的元素必然大于数组的最后一个元素。
  3. 故数据具有二段性,可以使用二分查找算法。

因为我们是和数组的最后一个元素比较,所以即使在数组完全旋转的特殊情况下也可以得到正确结果。 

而如果是和数组的第一个元素比较的话,在特殊情况时,还需特殊处理,这种解法留给大家,可以锻炼大家的代码能力以及加强对二分查找算法的理解。

 4.5.2 算法代码

class Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] <= nums[nums.length-1]) {right = mid;}else {left = mid + 1;}}return nums[left];}
}

4.6 题六:点名 (原:剑指Offer:0~n-1 中缺失的数字 )

 . - 力扣(LeetCode)

 4.6.1 思路分析

  1. 在数组中,缺失的数字前的数据其值与其下标是相对应的。
  2. 缺失的数字后的数据其值都比其下标大1,故数据具有二段性,可以使用二分查找算法。
  3. 第一个数值与下标不对应的数据的位置,就是缺失的数据。

特殊情况:缺的是最后一个数据时,数组中的所有数据与其下标均对应,此时需要特殊处理。

4.6.2 算法代码

class Solution {public int takeAttendance(int[] records) {int left = 0;int right = records.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (records[mid] > mid) {right = mid;}else {left = mid + 1;}}return records[left] == left ? left + 1 : left;}
}

END

这篇关于二分查找算法:朴素二分+左右边界二分力扣实战应用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Pandas使用SQLite3实战

《Pandas使用SQLite3实战》本文主要介绍了Pandas使用SQLite3实战,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录1 环境准备2 从 SQLite3VlfrWQzgt 读取数据到 DataFrame基础用法:读

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Python实战之屏幕录制功能的实现

《Python实战之屏幕录制功能的实现》屏幕录制,即屏幕捕获,是指将计算机屏幕上的活动记录下来,生成视频文件,本文主要为大家介绍了如何使用Python实现这一功能,希望对大家有所帮助... 目录屏幕录制原理图像捕获音频捕获编码压缩输出保存完整的屏幕录制工具高级功能实时预览增加水印多平台支持屏幕录制原理屏幕