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

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。

相关文章

PostgreSQL的扩展dict_int应用案例解析

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法
阅读更多...
MySQL中查找重复值的实现

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一：使用GROUP BY和HAVING子句方法二：仅返回重复值方法三：返回完整记录方法四：
阅读更多...
从原理到实战深入理解Java 断言assert

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言（assert）：从原理到实战引言：为什么需要断言？一、断言基础1.1 语
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
Python中re模块结合正则表达式的实际应用案例

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提
阅读更多...
Java MQTT实战应用

Java MQTT实战应用

《JavaMQTT实战应用》本文详解MQTT协议,涵盖其发布/订阅机制、低功耗高效特性、三种服务质量等级（QoS0/1/2）,以及客户端、代理、主题的核心概念,最后提供Linux部署教程、Sprin... 目录一、MQTT协议二、MQTT优点三、三种服务质量等级四、客户端、代理、主题1. 客户端（Clien
阅读更多...
在Spring Boot中集成RabbitMQ的实战记录

在Spring Boot中集成RabbitMQ的实战记录

《在SpringBoot中集成RabbitMQ的实战记录》本文介绍SpringBoot集成RabbitMQ的步骤,涵盖配置连接、消息发送与接收,并对比两种定义Exchange与队列的方式:手动声明(... 目录前言准备工作1. 安装 RabbitMQ2. 消息发送者（Producer）配置1. 创建 Spr
阅读更多...
深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器（Interceptor）与过滤器（Filter）深度解析：区别、实现
阅读更多...
深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制（JDK/CGLIB）、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实
阅读更多...
MySQL中的索引结构和分类实战案例详解

MySQL中的索引结构和分类实战案例详解

《MySQL中的索引结构和分类实战案例详解》本文详解MySQL索引结构与分类,涵盖B树、B+树、哈希及全文索引,分析其原理与优劣势,并结合实战案例探讨创建、管理及优化技巧,助力提升查询性能,感兴趣的朋... 目录一、索引概述1.1 索引的定义与作用1.2 索引的基本原理二、索引结构详解2.1 B树索引2.2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2