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

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

相关文章

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Python结合PyWebView库打造跨平台桌面应用

《Python结合PyWebView库打造跨平台桌面应用》随着Web技术的发展,将HTML/CSS/JavaScript与Python结合构建桌面应用成为可能,本文将系统讲解如何使用PyWebView... 目录一、技术原理与优势分析1.1 架构原理1.2 核心优势二、开发环境搭建2.1 安装依赖2.2 验

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

在Spring Boot中浅尝内存泄漏的实战记录

《在SpringBoot中浅尝内存泄漏的实战记录》本文给大家分享在SpringBoot中浅尝内存泄漏的实战记录,结合实例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录使用静态集合持有对象引用,阻止GC回收关键点:可执行代码:验证:1,运行程序(启动时添加JVM参数限制堆大小):2,访问 htt

SpringShell命令行之交互式Shell应用开发方式

《SpringShell命令行之交互式Shell应用开发方式》本文将深入探讨SpringShell的核心特性、实现方式及应用场景,帮助开发者掌握这一强大工具,具有很好的参考价值,希望对大家有所帮助,如... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL 分区与分库分表策略应用小结

《MySQL分区与分库分表策略应用小结》在大数据量、复杂查询和高并发的应用场景下,单一数据库往往难以满足性能和扩展性的要求,本文将详细介绍这两种策略的基本概念、实现方法及优缺点,并通过实际案例展示如... 目录mysql 分区与分库分表策略1. 数据库水平拆分的背景2. MySQL 分区策略2.1 分区概念

Spring Shell 命令行实现交互式Shell应用开发

《SpringShell命令行实现交互式Shell应用开发》本文主要介绍了SpringShell命令行实现交互式Shell应用开发,能够帮助开发者快速构建功能丰富的命令行应用程序,具有一定的参考价... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定义S