优选算法合集————双指针(专题三)

这期是双指针的第三期啦，还记得我们前几期讲了什么吗，是利用单调性，规律去利用双指针，还有滑动窗口的问题，本期我们带来二分查找的方法；

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

题目详解：

给了个数组和一个目标值，让我们在数组中寻找目标值，直接遍历时间复杂度为O(n)，但是用二分查找就是O(logn)了；

算法思路：

啥是二分查找呢，就是每次在一个空间中找到左边界和右边界，取两个边界的中间值，与目标值进行比较，在根据中间值缩小范围的过程；

1，定义三个指针，left=0，right=最右边的下标，mid

2，每次让mid等于left和right1的中间值，循环判断mid与target；

代码实现：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0,right = n-1;
        int mid = 0;
        while(left<=right){
            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;
    }
}

——————————————————————————————————————————

2，在排序数组中查找元素的第一个和最后一个位置

题目描述：

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 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]

题目详解：

这道题给了我们一个有序的数组，和一个目标值target，让我们找到数组中target的最左边和最右边，我们可以使用暴力查找，先找第一个符合target的值，之后再遍历找到第二个元素，但是题目是想让我们使用O(logn)时间复杂度的算法，二分查找中有个模版就是找左端点和右端点的方法，这题不卖关子了，我们直接使用二分查找；

算法思路：

1，我们先找左端点，二分查找中最重要的特性就是二段性，这道题就有二段性，我们看第一个例子，

比如例题上，我们的target等于8，找左端点，我们可以把数组分为两个部分，也就是二段性的精髓，左边的元素都小于target，右边的元素都大于target，我们来讨论一下中点mid落在不同区域的情况，

当mid元素落在区域的左边时，我们的mid该如何移动呢，因为左边是大于等于，所以有可能我们当前的mid元素就是我们的最左边了，所以我们的right最大限度只能更新到，rgiht下标，但是在mid<target区域，mid所指向的元素是不可能为target的，所以我们就大胆的往后移，left= mid+1，我们的大部分模版就完事了，那么就完事了吗，还有很多的注意事项，第一个就是循环条件，一定要是left<right，因为执行到这次循环之后，left就和right重合了，还有就是取中点的问题，我们学过第一种left+(right-left)/2，和第二种left+(right-left+1)/2；

这俩有啥区别呢，并且为啥要考虑这个呢，这个是端点二分模版中最容易发生死循环的地方，我们在偶数个数的数组中，

这个第一种的时候，出现的情况，

这是第二种的情况，现在看还好但是当只有两个元素的时候就会发生问题了，

​

看这时候，左端点为left，右端点为right，红色箭头是mid，当mid>=target的时候，我们把right = mid，这直接就死循环了，因为这时候就已经是right = mid，我们就进行不下去了，但是我们使用第一个的话，

当mid>=target的时候，右边的点会走到第一个之后重合，走出循环，当mid小于target的时候，left = mid加1，左边的节点就到右边了，重合，退出循环，这样我们就能成功找到左边的端点了，右边也是一样的，重新划分具有二段性的区域；

代码实现：

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


        left = 0;
        right = n-1;
        mid = 0;

        while(left<right){
            mid = left+(right-left+1)/2;
            if(nums[mid]<=target){
                left = mid;
            }else{
                right = mid-1;
            }
        }
        int b = left;
        if(nums[a]==target && nums[b]==target){
            return new int[]{a,b};
        }
        return new int[]{-1,-1};

    }
}

——————————————————————————————————————————

3，算法x的算术平方根

题目描述：

LCR 072. x 的平方根

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例 1：

输入: x = 4
输出: 2

示例 2：

输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2

题目详解：

这道题让我们自己模拟实现一个sqrt函数，数组是有序的，并且我们要找的数是<=一个数的，因为我们可以忽略小数部分，所有是有二段性的，我们可以使用二分查找的办法；

算法思路：

我们直接上一个图吧，

还是那个思路不过我们这次找一个端点就好了，还是开始讨论，循环条件left<right就好了，

判断中点条件时，我们就使用left+(right-left)来避免死循环；

代码实现：

class Solution {
    public int mySqrt(int x) {
        long left = 0;
        long right = (long)x;
        long mid = 0;
        while(left<right){
            mid = left+(right-left+1)/2;
            if(mid*mid<=x){
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return (int)left;
        
    }
}

——————————————————————————————————————————

4，搜索插入的位置

题目描述：

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 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

示例 4：

输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5：

输入: nums = [1], target = 0
输出: 0

题目详解：

这道题给我们了一个数组和一个目标值target，我们要找到比当前数组元素大或者相等的元素位置并且返回；

算法思路：

还是二段性，数组是有序的，左边的元素我们设置为严格小于目标值，而右边是大于等于target的，我们直接上图吧；

不多讲了嗷，好几遍了，都是一样的

代码实现：

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

——————————————————————————————————————————

5，山脉数组的峰顶索引

题目描述：

LCR 069. 山脉数组的峰顶索引

符合下列属性的数组 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 ，即山峰顶部。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [1,3,5,4,2]
输出：2

示例 3：

输入：arr = [0,10,5,2]
输出：1

示例 4：

输入：arr = [3,4,5,1]
输出：2

示例 5：

输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

提示：

题目详解：

这道题也是给了我们一个数组，让我们找到最大值，我们可以用暴力解法定义一个max，一个一个比较，但是我们有更快的方法，就是二分查找；

算法思路：

这道题也有二段性，数组是有序的，最大的点左边都满足当前节点比前一节点要大，山脉左边的节点都满足当前节点小于前一节点，正好满足二段性；

接下来套用模版就行了；

代码实现：

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

——————————————————————————————————————————

6，寻找峰值

题目描述：

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 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。

题目详解：

这道题给了我们一个数组，让我们找到一个峰值，和上一题是一样的但是有区别，就是这道题有很多的峰值，但是我们只需要返回一个就行了，这道题不好看，但是也是有二段性的，题意给了一个很重要的提示，就是num[0]和num[无穷]都是负无穷，我们只需要判断当前节点的下一个节点是什么就行了，我们在算法思路中画图；

算法思路：

我们需要分类讨论当前节点与下一节点的关系；

我们看当前情况当arr[i]<arr[i+1]时说明正在呈上升趋势，我们学过抛物线吧，右边是负无穷，所以峰值很可能在右边，我们让left = mid;

这次是当前节点小于下一个节点了，这说明了峰值节点可能再最左边，注意啊，这次是不会有arr[i]==arr[i+1]的情况了，因为找的是峰值，我们再来总结一下啊，

并且判断一下中点，避免超时，这里告诉大家一个小技巧，我们right=mid那么就在左边，如果在右边的话就会有超时，同理left = mid的话就在右边，就是中点落在后边的left+(right-left+1)/2；

代码实现：

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

——————————————————————————————————————————

7，寻找旋转排序数组中的最小值

题目描述：

153. 寻找旋转排序数组中的最小值

已知一个长度为 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 次得到输入数组。

题目详解：

这道题给了我们一个数组，并对数组进行了旋转操作，旋转操作是把最后一个元素移到最前面，我们会得到一个旋转之后的数组，我们要在旋转数组中找到最小值；

算法思路：

这道题可以直接使用暴力查找，定义一个变量min直接找最小的，我们怎么可以使用这样的办法呢，我们来看个图

大家有没有发现这道题的二段性呢，左边的数会始终大于arr[n-1]的数，就是数组中最后一个数，而右边的数始终小于等于arr[n-1]，这下很明显了吧，我们在来做个归纳，

直接代入模版，考虑中点超时情况就好了；

代码实现：

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

——————————————————————————————————————————