【Leetcode】解锁二分查找：突破解题瓶颈的关键技巧

前言

🌟🌟本期讲解关于力扣的几篇题解的详细介绍~~~

🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客

🔥 你的点赞就是小编不断更新的最大动力

🎆那么废话不多说直接开整吧~~

📚️1.朴素二分

🚀1.1二分查找

1.1.1题目解析

1.1.2算法分析

1.1.3代码编写

1.1.4时间复杂度

📚️2.非朴素二分

🚀2.1查找排列数组中元素第一个和最后一个位置

2.1.1题目解析

2.1.2算法分析

2.1.3代码编写

🚀2.2总结非朴素二分模版

📚️3.总结

📚️1.朴素二分

🚀1.1二分查找

1.1.1题目解析

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

当然题目很好理解，就是寻找一个目标值，然后返回目标值的下标，若没有就返回-1；那么如下例题所示：

1. 输入: nums= [-1,0,3,5,9,12], target= 9

输出: 4 解释: 9 出现在 nums中并且下标为 4

2. 输入：nums = [-1,0,3,5,6]，target = 4

输出：-1

接下来就是小编对于这道题的理解

1.1.2算法分析

第一种：利用暴力算法

思路：不断循环遍历枚举，然后进行比较，若找到了就返回数组的下标；若目标值小于此时遍历的数组的某个元素，那么由于数组的升序排序的缘故，直接返回-1即可

这里小编就不在进行代码编写了，比较简单

第二种：二分查找

什么是二分查找：

其实所谓的二分查找就是找出一个数组的二段性，然后根据这个二段性将数组分为两个部分，然后其中一部分可以进行舍去；（所以不管数组是否是升序还是乱序，找到二段性就可以使用二分算法）

思路分析：

具体思路就是在数组的左边和右边端点设置两个指针，指针之间就是一个区间，然后算出两个指针的中点，和左右指针分为两个部分，其中一部分小于或者大于就要更新区间范围；

如下图所示：

小编字写得不是很好，请见谅~~~

我们算出中点后，判断中点的值 nums[mid] 是否小于或者大于目标值target；

若小于target：说明mid落在【left-target】之间，那么缩小范围就是left = mid + 1；

若大于target：说明mid落在【target - right】之间，那么缩小范围就是right = mid - 1；

若等于目标值那么就可以直接返回即可；

我们举一个例子如下所示：

那么此时，一下就可以干掉一大部分的没有遍历意义的数据，直接快了许多；

1.1.3代码编写

具体的代码如下所示：

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

这里的求中点的算法，为啥不直接left + right /2呢？小编这种是为了防止溢出的风险，所以小编使用减法实现的，就不会溢出了，这里使用的循环条件判断，假如所有的值都小于target，那么left会一直加，直到等于right，此时再次判断，那么不等于target，那么就直接返回-1即可了；

提示：一般优点难度的二分查找都不会使用这里的朴素二分，所以这道题模版就不进行编写了；

1.1.4时间复杂度

由于二分算法使用是每次干掉一半的数值；

第 1 次查找：在长度为的区间内查找，比较中间元素后，剩余待查找区间长度变为n/2 。
第 2 次查找：基于上一次缩小后的区间，再比较中间元素，此时剩余待查找区间长度变为n/2*2 。
第 3 次查找：同理，剩余待查找区间长度变为n/2*2*2 。
以此类推：经过 k次查找后，剩余待查找区间长度变为n/2*2...... 。

所以经过变换后，两边同时以2为底的对数后，在算法复杂度分析中，通常忽略对数的底数（因为不同底数的对数之间仅相差一个常数因子）时间复杂度就是：logN

📚️2.非朴素二分

🚀2.1查找排列数组中元素第一个和最后一个位置

2.1.1题目解析

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

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

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

其实大概意思就是：

在 5 5 7 7 8 8 8 9中查找8，那么开始位置为4，最后一个位置为6，那么输出就是[4 , 6]

2.1.2算法分析

小编这里不进行暴力算法的分析了，直接步入正题

1.查找区间的左端点

其实这里的元素可以分为两部分：

如上图：第一部分是全部小于target的，那么另一部分就是全都大于或者等于target的；

所以根据二段性，此时就可调整区间了

num[mid] < target，在区间一号位，那么left = mid + 1，此时不肯能等于mid，因为mid指定的数本来就小于target，那么left 更新为mid + 1就可以了；

num[mid] >= target，那么在区间二号位，所以right = mid就可以了，为啥不是mid - 1，因为right刚好等于区间左端点的话，mid - 1就会超出正确区间；

细节问题：

1.这里使用left < right ，还是 left < = right 呢？

答案是left < right ：

假如我们是left <= right，咱们看看一下例子：

2 2 3 3 4 4, target = 1

那么此时就会满足大于 target ,此时right 就会一直加加，直到等于left ，那么此时一直等于left，mid又大于target，right = mid, 但是mid = right = left ，此时就会进入死循环

2.取中点的时候使用left + (right - left)/2;还是left + (right - left + 1)/2;

此时我们还是举一个例子：

假如我们使用left + (right - left + 1)/2;

如下：

但是使用left + (right - left)/2;就不会出现这种情况；

2.查找区间右端点

如下图所示：

具体的步骤和上面区间左端点一致；

1.x <= target 的时候，在区间右端，那么left = mid，假如正好是花圈的位置，就不能+1，所以为left = mid;

2.x > target的时候，子啊区间左端，right = mid - 1;

细节问题：

此时right > left，这个是一致的，相遇了判断即可，无需进行循环；

但是在 left + (right - left)/2里会有一个缺陷：

那么就直接使用 left + (right - left + 1)/2；

2.1.3代码编写

代码如下所示：

class Solution {public int[] searchRange(int[] nums, int target) {int[] ret = new int[2];ret[0] = ret[1] = -1;if (nums.length == 0) {return ret;}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;}}if(nums[left] != target){return ret;}else{ret[0] = left;}//计算右端点right = nums.length-1;while(left < right){int mid = left + (right - left + 1)/2;if(nums[mid] > target){right = mid - 1;}else{left = mid;}}ret[1] = left; return ret;}
}

这里先求出左端点要用素组存储，然后计算出右端点后再进行存储；

🚀2.2总结非朴素二分模版

查找左端点：

  while(left < right){int mid = left + (right - left)/2;if(......){left = mid + 1;}else{right = mid;}}

查找右端点：

   while(left < right){int mid = left + (right - left + 1)/2;if(.....){right = mid - 1;}else{left = mid;}}

注意了：

1.循环条件一直就是right > left

2.不知道是否是left + (right - left + 1)/2还是left + (right - left )/2;观察如果right = mid - 1，那么就是left + (right - left + 1)/2;如果right = mid，没有减去一，那么就是left + (right - left )/2;