【算法系列篇】二分查找——这还是你所知道的二分查找算法吗？_二分查找的时间复杂度-程序员宅基地
文章目录
前言
在生活中，我们往往会遇到在数组中查找某个确定的元素的时候，通常我们会选择使用暴力解法，这样虽然简单，但是时间复杂度是O(N)，时间效率比较低。那么是否有方法可以使得在具有二段性的数组中找某一特定的元素的时间复杂度低于0(N)呢？答案是肯定的，当我们可以将数组分为两个部分的时候，也就是数组具有二段性的时候，可以使用二分查找的算法来进行高效的查找。通常二分查找的时间复杂度为O(logN)。那么这篇文章我将为大家分享关于二分查找的知识。
什么是二分查找算法
二分查找算法（Binary Search Algorithm）是一种在有序数组（但不仅限于有序数组）中查找特定元素的搜索算法。它采用分治策略，每次比较数组中间的元素，如果该元素等于目标值，则搜索结束，否则根据目标值与中间元素的大小关系，将搜索范围缩小为数组的左半部分或右半部分，然后在新的搜索范围内重复执行上述操作，直到找到目标值或确定目标值不存在于数组中。
二分查找算法的时间复杂度为O(log n)，其中n为数组的长度。由于每次都能排除一半的元素，因此算法的效率非常高，尤其适用于大规模数据的查找操作。
其实二分查找算法本来并不难，只是实现二分查找算法时，需要注意一些细节，例如处理数组边界、处理相等的情况等。如果没有处理好边界和相等问题的时候，很容易造成死循环。
1.二分查找
https://leetcode.cn/problems/binary-search/
1.1 题目要求
给定一个 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
提示：
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间。
class Solution {
public int search(int[] nums, int target) {
}
}
1.2 做题思路
因为这道题目给的数组是有序的，我们 定义两个变量 left 和 right 分别从数组的开头和末尾开始，求 left 和 right 和的平均值的下标 mid ，然后看 mid 下标所代表的值与 target 的关系，如果 nums[mid] > target ，则可以确定在 [mid,right] 之间没有我们要找的 target 值，所以直接将这一半的数据给“舍弃”，将 right 的值更改为 mid - 1；如果 nums[mid] < target，则说明在 [left,mid] 这一范围内，没有我们需要找的 target 值，将这一部分给“舍弃”，left 的值更新为 mid + 1；如果nums[mid] = target，则返回 mid 的下标。 当然，这只是一种确定区间的方法，也可简单的称为“左闭右闭”，还有“左闭右开"、“左开右闭”这两种确定区间的方法，这两种方法是差不多的，那么就以“左闭右开”这种方式为大家介绍一下。我们前面为大家说明的是“左闭右闭”这种确定区间的方式，左闭右闭是指：left 和 right 这两个值，我们都可以取到，而左闭右开或者左开右闭则只是 left 或者 right 的数据可以取到。确定区间的方式不同，我们最终的循环条件也不同，究竟是 left < right，还是 left <= right，这就取决于我们区间的确定方式，如果是以“左闭右闭”的方式确定的，则需要加上等号，另外两种方式则不需要。 为什么呢？大家可以看看下面的图。
我们就以上面所讲的基本的二分查找算法来看看这道题目该怎么做。
1.3 Java代码实现
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;
}
}
求 mid 的方式有两种，一种是 left + (right - left) / 2，一种是 left + (right - left + 1) / 2，这两种求 mid 的方式在这道题目是没什么区别的，具体的区别在后面的题目会遇到。
但是为什么我们不直接用 mid = (right - left) / 2 呢？因为我们不知道数组的大小为多少，很可能会造成 int 或者 long 类型不能够存储 left + right的值。
2.在排序数组中查找元素的第一个和最后一个位置
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
2.1 题目要求
给你一个按照非递减顺序排列的整数数组 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
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
class Solution {
public int[] searchRange(int[] nums, int target) {
}
}
2.2 做题思路
做这道题目，如果使用和上面一样的思想的话，时间复杂度会降到 O(N)，为什么呢？因为当你找到目标值之后，你还需要找到这个数的起始位置和结束位置，假设我们想要找的数是3，而数组中的数字全是3的话，那么就需要遍历整个数组一遍，时间复杂度就会降到 O(N)，所以我们也就不能使用跟上面一样的思路，也就是朴素二分法，这道题需要我们使用到非朴素的二分算法，朴素算法其实是将数组分成了三个部分，小于目标值的部分，等于目标值的部分和大于目标值的部分，而非朴素算法则是真正的将数组分成了两个部分：小于等于目标值的部分和大于目标值的部分或者是小于目标值的部分和大于等于目标值的部分。这道题就是非朴素算法的思路，将数组分为了两个部分。
寻找左边界的时候，如果 nums[mid] < target ，则说明 mid 在小于目标值的那一部分，这部分肯定没有我们需要的数字，所以将 left 改为 mid + 1，而如果
numd[mid] >= target 的时候，就不能将 right 改为 mid - 1了，因为这个 mid 值可能刚好是我们需要找的值，所以将 right 的值改为 mid 而不是 mid - 1
在寻找有边界的时候，数组被分为了小于等于和大于目标值的两部分，当
nums[mid] <= target 的时候，因为 mid 所指向的位置可能是我们要找的值，所以 left = mid，当 nums[mid] > target 的值，因为在 [mid,righ] 之间肯定没有我们想要找的值，所以right = mid - 1.
数组分为不同的两部分，求 mid 的方法也是不同的，这也就是上面说的 mid = left + (right - left) / 2 和 mid = left + (right - left + 1) / 2的区别。
注意了，循环条件一定不能加等号，因为当left = right的时候，这个相遇的值恰好是我们需要的值，所以没必要多判断一次，更重要的是会陷入死循环。
2.3 Java代码实现
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[]{
-1,-1};
int n = nums.length;
if(n == 0) return ret; //当数组大小为0时，直接返回
int left = 0;
int right = n - 1;
//求目标值的第一个位置
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] < target) {
left = mid + 1;
}else {
right = mid;
}
}
if(nums[left] == target) ret[0] = left; //判断数字中是否存在目标值
right = n - 1;
//求目标值的最后一个位置
while(left < right) {
int mid = left + (right - left + 1) / 2;
if(nums[mid] > target) {
right = mid - 1;
}else {
left = mid;
}
}
if(nums[left] == target) ret[1] = left;
return ret;
}
}
3.搜索插入位置
https://leetcode.cn/problems/search-insert-position/
3.1 题目要求
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 为 无重复元素 的 升序 排列数组
- -104 <= target <= 104
class Solution {
public int searchInsert(int[] nums, int target) {
}
}
3.2 做题思路
根据题目，我们可以知道，这个题目大致分为两种情况：目标值在数组中，返回目标值的下标，如果目标值不存在则返回目标值应该插入位置的下标。
可以将数组分为两个部分，这就可以用到我们的二分查找算法了。
3.3 Java代码实现
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0;
int right = n - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] < target) {
left = mid + 1;
}else {
right = mid;
}
}
if(nums[left] < target) return left + 1; //当待插入位置位于数组的末尾时，需要作出判断
else return left;
}
}
4.x的平方根
https://leetcode.cn/problems/sqrtx/
4.1 题目要求
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
- 0 <= x <= 231 - 1
class Solution {
public int mySqrt(int x) {
}
}
4.2 做题思路
如果 x 的平方根为整数的话，则直接返回，如果不是整数的话，则返回平方小于 x 的最大整数，通过这样理解题目，我们也可以将数组分为两个部分，小于等于 x 的部分和大于 x 的部分。同样，使用二分查找的算法解决。
4.3 Java代码实现
class Solution {
public int mySqrt(int x) {
long left = 0; //这里mid * mid可能会很大，超出 int 所能表示的范围，所以我们用 long 来表示
long right = x;
while(left < right) {
long mid = left + (right - left + 1) / 2;
if(mid * mid > x) {
right = mid - 1;
}else {
left = mid;
}
}
return (int)left;
}
}
5.山脉数组的峰顶索引
https://leetcode.cn/problems/peak-index-in-a-mountain-array/
5.1 题目要求
符合下列属性的数组 arr 称为 山脉数组 ：
- arr.length >= 3
- 存在 i（0 < i < arr.length - 1）使得：
-
- arr[0] < arr[1] < … arr[i-1] < arr[i]
-
- arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。
- arr[i] > arr[i+1] > … > arr[arr.length - 1]
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1：
输入：arr = [0,1,0]
输出：1
示例 2：
输入：arr = [0,2,1,0]
输出：1
示例 3：
输入：arr = [0,10,5,2]
输出：1
提示：
- 3 <= arr.length <= 105
- 0 <= arr[i] <= 106
- 题目数据保证 arr 是一个山脉数组
class Solution {
public int peakIndexInMountainArray(int[] arr) {
}
}
5.2 做题思路
因为题目保证数组 arr 是一个山脉数组，有很明显的二段性，所以很容易想到二分查找的算法。
将数组分为两部分：小于峰顶值的部分和大于等于峰顶值的部分。当 mid 落在小于峰顶值的部分时，我们使 left = mid + 1，如果 mid 落在 大于等于峰顶值的部分时，令right = mid。
5.3 Java代码实现
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0;
int right = arr.length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(arr[mid] < arr[mid + 1]) {
left = mid + 1;
}else {
right = mid;
}
}
return left;
}
}
6.寻找峰值
https://leetcode.cn/problems/find-peak-element/
6.1 题目要求
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
提示：
- 1 <= nums.length <= 1000
- -231 <= nums[i] <= 231 - 1
- 对于所有有效的 i 都有 nums[i] != nums[i + 1]
class Solution {
public int findPeakElement(int[] nums) {
}
}
6.3 做题思路
注意看题目，题目中给了，可以假设 nums[-1] = nums[n] = 负无穷，所以可以将数组看成是从负无穷加到一个峰值，然后再从峰值减小到负无穷，即使你数组中的元素是单调的，也会形成山峰的形状，很明显的二段性，所以使用二分查找的算法。同样将数组分为两部分：小于峰值的部分和大于等于峰值的部分。
6.4 Java代码实现
class Solution {
public int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] < nums[mid + 1]) {
left = mid + 1;
}else {
right = mid;
}
}
return left;
}
}
7.寻找旋转数组中的最小值
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
7.1 题目要求
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
- 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- nums 中的所有整数 互不相同
- nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
class Solution {
public int findMin(int[] nums) {
}
}
7.2 做题思路
无论数组旋转多少次，总会将前面部分的升序数组给旋转到后面部分数组的后面，通过画图我们可以看出，这又是明显的具有二段性的数组，可以使用二分查找的算法来解决。
数组的两个部分中，较大的部分中的所有元素都大于较小数组部分的最大值，而我们要找的最小的值也就是在较小的那一部分中，所以我们将数组分为大于 nums[n-1] 的部分和小于等于nums[n-1] 两部分，当 mid 落在大于 nums[n-1] 的部分时，left = mid + 1，当 mid 落在小于等于 numd[n-1] 的部分时，right = mid。
7.3 Java代码实现
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int left = 0;
int right = n - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] > nums[n-1]) {
left = mid + 1;
}else {
right = mid;
}
}
return nums[left];
}
}
总结
其实二分查找这个算法不算难，只要主要好边界条件、区间，不造成死循环其实就很简单，只要知道了可以将数组分为哪两部分，就可以直接套模板，通过看上面几道题目的代码我们也可以看出，代码基本上类似，所以大家只要能够将数组分为两部分和不同部分区间的变化条件和区间的变化就可以了。
智能推荐
SpringBoot如何手动注册Bean_springboot 手动注册bean-程序员宅基地
文章浏览阅读4.9k次。如何手动注册Bean 技术介绍BeanDefinitionRegistryPostProcessor部分上文所述实体类TestBeanTestFactory extends FactoryBean注册所用接口 TestService技术介绍BeanDefinitionRegistryPostProcessor部分BeanDefinitionRegistryPostProcessor是springboot手动注册bean 的组件之一，于其相似的还有importBeanDefinitionRegistra_springboot 手动注册bean
centos xampp升级mysql_CentOS下安装XAMPP详细教程-程序员宅基地
文章浏览阅读108次。现在php的集成运行环境越来越多，个人比较喜欢XAMPP，更新速度快，好用，安装便捷。windows下面的安装，就是下一步、下一步，没什么好说的，详细说一下linux下面的安装，这里以CentOS为例进行说明。一、 下载XAMPP如果直接使用wget从xampp的官网上下载，由于各种墙，不能下载成功，可以在该链接中选择自己需要的版本。我选择的linux下，64位，5.6.14这个版本。使用以下..._centeros 升级 xampp
免费可用的Android手机传感器数据采集程序（附程序）_手机原始加速度传感器 采集-程序员宅基地
文章浏览阅读6.6k次，点赞8次，收藏61次。免费可用的Android手机传感器数据采集程序（附程序）Sensor sense简介该APP可以采集各种传感器的数据，并且实现数据可视化，在个人科研工作中可视化对于我用处颇多，比如3轴加速度计数据的可视化如下。其中给我直观的数据感受尤其重要。该APP支持超过10种传感器，基本覆盖了现在我们开发常用的传感器（视觉相机除外）。其中传感器包括：压力、光照强度、位置、移动网络、WiFi、加速度、磁场、重力、步数计算接口、陀螺仪、旋转向量、声强。1.1主界面：1.2子界面：采集界面有实时的数据可视化_手机原始加速度传感器 采集
Github 2023-12-14开源项目日报 Top10-程序员宅基地
文章浏览阅读1.1k次，点赞23次，收藏24次。根据Github Trendings的统计，今日(2023-12-14统计)共有10个项目上榜。
java js文件上传excel_EXCEL文件下载（js、java）-程序员宅基地
文章浏览阅读130次。下载的js：/*** @param target_URL 下载地址* @param onload 服务器返回结果的回调函数* @param fileName 文件名 不传则从服务端获取 Content-disposition filename=** @param save_URL 保存路径 先不写了*/function downLoadFile(target_url,onloadFunction,..._jquery前端上传下载excel文件,后端java
IntelliJ IDEA 2022.1 安装教程_idea2022.1-程序员宅基地
文章浏览阅读7.9w次，点赞158次，收藏1.2k次。IntelliJ IDEA 2022.1 保姆级安装教程_idea2022.1
随便推点
【2022最新Java面试宝典】—— SpringCloud面试题（49道含答案）-程序员宅基地
文章浏览阅读3.9w次，点赞120次，收藏1.3k次。目录Spring Cloud1. 什么是微服务架构2. 为什么需要学习Spring Cloud3. Spring Cloud 是什么4. SpringCloud的优缺点5. SpringBoot和SpringCloud的区别？6. Spring Cloud和SpringBoot版本对应关系7. SpringCloud由什么组成8. 使用 Spring Boot 开发分布式微服务时，我们面临什么9. Spring Cloud 和dubbo区别?Eureka10. 服务注册和发现是什么意思？Spring Clo_springcloud面试题
用无代码搭建数据中台，竟做到如此丝滑_数据中台代码-程序员宅基地
文章浏览阅读1.4w次，点赞105次，收藏103次。要说数据中台用无代码平台构建可能大多数人不信，但smardaten确实有一点不容忽视，就是这个开发平台本身远远不止无代码开发。smardaten是一个以数据驱动的无代码平台，平台的前身就是大数据平台。现在把数据能力作为平台底层核心能力，包含了大多常见的数据处理能力。smardaten主要满足行业级复杂应用的开发，而不是通常的轻量级开发，由于自带大数据底座，数据层面可以减少大量的数据集成、数据清洗、数据治理、接口管理等开发工作，大大减少了业务系统的开发难度和设计难度。_数据中台代码
利用matlab实现DMD动态模态分解(在一维信号或二维流场矢量中的应用）_dmd分解-程序员宅基地
文章浏览阅读3.1w次，点赞109次，收藏372次。利用matlab实现DMD解(在一维信号或二维流场矢量中的应用）0 前言0.1 特征根的计算与含义1 DMD的基本思路2 一维DMD算法_dmd分解
使用STS或Eclipse配置内容助理（Java代码提示）的方法_sts输入助手-程序员宅基地
文章浏览阅读1.1w次。默认情况下只有我们在按下“.”的时候才会有代码提示，使用visual studio时看到这个IDE是按下所有的键都会自动提示，以前还很羡慕visual studio的强大，有一天才发现，原来eclipse也有这个功能，但是默认没有开启。开启方法如下：windows-->Preferences-->Java-->Editor-->Content Assist在Auto activation _sts输入助手
Python - Sublime Text 3 控制台不能输出中文的解决方法_sublime控制台输出不了中文-程序员宅基地
文章浏览阅读311次。Python - Sublime Text 3 控制台不能输出中文的解决方法_sublime控制台输出不了中文
横向移动之IPC&WMI&SMB&CrackMapExec密码喷射_横向移动cme-程序员宅基地
文章浏览阅读391次。IPC攻击流程：建立ipc$连接 --> copy命令上传后门文件 --> at命令计划任务执行后门文件，上线WMI&SMB攻击流程：抓取账号密码(需提权) --> 将后门放到web根目录下 -->套件或工具进行横向移动，执行命令下载web下的后门文件然后执行，上线CME工具：进行密码喷射，利用smb服务进行批量验证账密，执行命令下载后门然后执行，上线。_横向移动cme