LeetCode 二分专题

﹏ヽ暗。殇╰゛Y 2022-10-17 01:53 168阅读 0赞

这是整理的LeetCode上的二分专题，先按照codeTop上的频率顺序从高到低进行整理，然后按别人整理的进行再次整理。

# 二分搜索概述 #

先不从具体题来出发，而先从二分查找可能解决的问题出发。  
二分查找最常见的两个场景：

*  寻找一个数
 *  寻找边界
    
     *  寻找左边界
     *  寻找右边界

场景不同会导致二分查找中细节的不同，所以要应对大部分题目，就需要把这两种场景搞清楚。

首先二分查找最基础的框架如下：

int binarySearch(vector<int> nums, int target) {
        
        int left = 0, right = ...;
    
        while(...) {
        
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
        
                ...
            } else if (nums[mid] < target) {
        
                left = ...
            } else if (nums[mid] > target) {
        
                right = ...
            }
        }
        return ...;
    }

我们在写二分查找时，最好不要写else，而是把所有情况用else if写清楚。  
计算mid时为了防溢出，使用 `int mid = left + (right - left) / 2;` 进行计算。  
而`...`中就是二分查找中的一些关键细节，比如：

*  while()中的 left 是小于(<) right，还是小于等于(<=)right
 *  mid是否加减一

--------------------

# 二分查找典型题目 #

我们先举出最基础的一个二分搜索题目（场景1—寻找一个数）：

## 场景一：寻找一个数 ##

[704. 二分查找][704.]  
给定一个 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

直接贴代码：

class Solution {
        
    public:
        int search(vector<int>& nums, int target) {
        
            int l = 0, r = nums.size()-1;
            while(l <= r){
        
                int mid = (l + r) / 2;
                if(nums[mid] == target) return mid;
                else if(nums[mid] < target) l = mid+1;
                else r = mid-1;
            }
            return -1;
        }
    };

细节：

*  `l <= r`：为什么是小于等于，这是因为如果没有找到target，就需要while循环终止返回-1。  
    “没有找到”即“搜索区间为空”，而 `l <= r` 的终止条件为 `l == r+1`，区间形式为\[r+1, r\]，这样就能跳出循环返回-1，而 `l < r` 的终止条件为 `l == r`，区间形式为\[r, r\]，然而这时区间非空，但这时while循环终止了，r这个索引的数还没搜索，返回-1是有问题的，所以我们要小于等于。
 *  `l = mid+1; r = mid-1;` ：这个很简单，因为两端是闭区间，当前mid不符合，把mid剔除掉区间肯定要加减一的。

--------------------

## 场景二-1 寻找左边界 ##

假设有序数组 nums = \[1,2,2,2,3\]，target为2，如果我们希望找到target的左侧边界，上面算法在面对这样场景是无法解决的。

[34. 在排序数组中查找元素的第一个和最后一个位置][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\]

本题查找元素的第一个和最后一个位置，而第一个位置就是寻找左边界。

int left_bound(vector<int>& nums, int target){
        
        // 二分法找左边界
        int l = 0, r = nums.size()-1;
        while(l < r){
        
            int mid = l + (r - l) / 2;
            if(nums[mid] == target){
        
                r = mid;
            }
            else if(nums[mid] < target){
        
                l = mid+1;
            }
            else if(nums[mid] > target){
        
                r = mid-1;
            }
        }
        int left = l != nums.size() && nums[l] == target ? l : -1;
        return left;
    }

[278. 第一个错误的版本][278.]

假设你有 n 个版本 \[1, 2, …, n\]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

本题其实也是查找最左边界，只是条件只有两种情况true or false

class Solution {
        
    public:
        int firstBadVersion(int n) {
        
            // 二分
            int l = 1, r = n;
            while(l < r){
         // 循环直至区间左右端点相同，即最终到[l, l]退出
                int mid = l + (r - l) / 2;
                if(isBadVersion(mid)){
        
                    r = mid; // 区间为[l, mid]中
                }else{
        
                    l = mid+1; // 区间为[mid+1, r]中
                }
            }
            return l;
        }
    };

## 场景二-2 寻找右边界 ##

同样在[34. 在排序数组中查找元素的第一个和最后一个位置][34.] 此题中，我们要找到最后一个位置，即寻找到右边界。

如果我们仅仅修改上面寻找左边界的

if(nums[mid] == target){
        
    	r = mid;
    }

为

if(nums[mid] == target){
        
    	l = mid;
    }

是错的，这是因为当区间最后为\[l, l+1\]时，mid一直为l，而l也一直为mid，这样就无法跳出循环。  
因此我们的代码修改如下：

int right_bound(vector<int>& nums, int target){
        
        // 二分法找右边界
        int l = 0, r = nums.size()-1;
        while(l <= r){
         // 循环直至[r+1, r]时退出 
            int mid = l + (r - l) / 2;
            if(nums[mid] == target){
        
                l = mid+1; // 区间变为[mid+1, r]
            }
            else if(nums[mid] < target){
        
                l = mid+1; // 区间变为[mid+1, r]
            }
            else if(nums[mid] > target){
        
                r = mid-1; // 区间变为[l, mid-1]
            }
        }
        int right = r != -1 && nums[r] == target ? r : -1;
        return right;
    }

我们可以知道这样就避免我们上面提出的问题。while循环中条件改为 l <= r，且当 nums\[mid\] == target  
时l = mid+1，这样如果target在数组中存在那么最后r就是我们要找的右边界。

# 旋转数组专题 #

## [153. 寻找旋转排序数组中的最小值][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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 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 次得到输入数组。

排序题一般使用二分法求解。  
我们求得中间值，我们比较nums\[mid\]与nums\[r\]：

*  nums\[mid\] < nums\[r\]：说明mid在后面的非递减序列中，有可能nums\[mid\]是最小值，所以我们的范围变成\[l, mid\]
 *  nums\[mid\] > nums\[r\]：说明mid在前面的非递减序列中，必然不是最小值，因此我们的范围变成\[mid+1, r\]

class Solution {
        
    public:
        int findMin(vector<int>& nums) {
        
            int l = 0, r = nums.size()-1;
            while(l < r){
        
                int mid = l + (r - l)/2;
                if(nums[mid] > nums[r]){
        
                    l = mid+1;
                }
                else{
        
                    r = mid;
                }
            }
            return nums[l];
        }
    };

## [154. 寻找旋转排序数组中的最小值 II][154. _ II] ##

这题在上一题的基础上多加了重复的条件，因此有三种情况：

*  nums\[mid\] < nums\[r\]：说明mid在后面的非递减序列中，有可能nums\[mid\]是最小值，所以我们的范围变成\[l, mid\]
 *  nums\[mid\] > nums\[r\]：说明mid在前面的非递减序列中，必然不是最小值，因此我们的范围变成\[mid+1, r\]
 *  nums\[mid\] = nums\[r\]: r–

class Solution {
        
    public:
        int findMin(vector<int>& nums) {
        
            int l = 0, r = nums.size()-1;
            while(l < r){
        
                int mid = l + (r - l) / 2;
                if(nums[mid] < nums[r]){
        
                    r = mid;
                }else if(nums[mid] > nums[r]){
        
                    l = mid+1;
                }else{
        
                    r -= 1;
                }   
            }
            return nums[l];
        }
        
    };

## 33. [搜索旋转排序数组][Link 1] ##

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 \[nums\[k\], nums\[k+1\], …, nums\[n-1\], nums\[0\], nums\[1\], …, nums\[k-1\]\]（下标 从 0 开始 计数）。例如， \[0,1,2,4,5,6,7\] 在下标 3 处经旋转后可能变为 \[4,5,6,7,0,1,2\] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

> 输入：nums = \[4,5,6,7,0,1,2\], target = 0  
> 输出：4

示例 2：

> 输入：nums = \[4,5,6,7,0,1,2\], target = 3  
> 输出：-1

示例 3：

> 输入：nums = \[1\], target = 0  
> 输出：-1

注意这里的题干说到数组中的数字各不相同，也就是说如果一个递增序列nums=\[1, 2, 3, 4, 5\] 经过旋转，得\[3, 4, 5, 1, 2\]，那么nums\[0\] > nums\[4\]，target = 2  
我们可以通过二分法求得  
\[3, 4, 5, 1, 2\] 初始左边界下标为0，右边界下标为4，mid = 2，然后我们判断\[l, mid-1\]是有界还是\[mid, r\]是有界的。

*  如果 target 刚好等于 nums\[mid\]，则直接返回mid；
 *  如果\[l, mid-1\]是有序的，且nums\[l\] <=target<=nums\[mid-1\]这个范围，那么就把 r = mid-1，否则 l = mid+1；
 *  如果\[mid, r\]是有序的，且nums\[mid\] <=target<=nums\[r\]这个范围，那么就把 l = mid+1，否则 r = mid-1。

class Solution {
        
    public:
        int search(vector<int>& nums, int target) {
        
            int n = nums.size();
            if (!n) {
        
                return -1;
            }
            if (n == 1) {
        
                return nums[0] == target ? 0 : -1;
            }
            int l = 0, r = n - 1;
            while (l <= r) {
        
                int mid = (l + r) / 2;
                if (nums[mid] == target) return mid;
                if (nums[0] <= nums[mid]) {
         // [l, mid-1]是有序
                    if (nums[0] <= target && target < nums[mid]) {
        
                        r = mid - 1;
                    } else {
        
                        l = mid + 1;
                    }
                } else {
        //[mid, r]是有序
                    if (nums[mid] < target && target <= nums[n - 1]) {
        
                        l = mid + 1;
                    } else {
        
                        r = mid - 1;
                    }
                }
            }
            return -1;
        }
    };

--------------------

## [81.搜索旋转排序数组 II][81._ II] ##

已知存在一个**按非降序排列**的整数数组 nums ，数组中的值**不必互不相同**。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 \[nums\[k\], nums\[k+1\], …, nums\[n-1\], nums\[0\], nums\[1\], …, nums\[k-1\]\]（下标 从 0 开始 计数）。例如， \[0,1,2,4,4,4,5,6,6,7\] 在下标 5 处经旋转后可能变为 \[4,5,6,6,7,0,1,2,4,4\] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

> 输入：nums = \[2,5,6,0,0,1,2\], target = 0  
> 输出：true

示例 2：

> 输入：nums = \[2,5,6,0,0,1,2\], target = 3  
> 输出：false

这题与上题的唯一区别在于这里的数组中可以存在着相等的数，即非递减数组，那么就会存在一些与上题做法不符合的特例，如

> \[1, 1, 1, 0, 1\]  
> 我们可以发现如果nums\[2\] = 1，而我们无法通过nums\[0\] 与 nums\[mid\]的大小来判断\[l, mid-1\]是有序，还是\[mid, r\]是有序的。

所以可以换一种思路，在剑指offer第11题 旋转数组的最小数字中，通过比较mid与nums\[r\]的大小关系来判断mid在前面的递增序列中还是在后面的递增序列中。

*  mid < nums\[r\]：说明mid在后面的非递减序列中
 *  mid > nums\[r\]：说明mid在前面的非递减序列中
 *  mid == nums\[r\]：令r–

举个栗子：

> \[1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1\] target = 2  
> 我们可以看到nums\[mid\] = 1 == nums\[r\]，所以r–  
> 直到nums\[r\] = 2.因此nums\[mid\] = 1 < nums\[r\] = 2，表示\[mid, r\]为非递减序列并且2在\[mid, r\]范围，那么说明我们在\[mid,r\]这个范围去搜索。

class Solution {
        
    public:
        bool search(vector<int> &nums, int target){
        
            int n = nums.size();
            if(!n){
        
                return false;
            }
            if(n == 1){
        
                return nums[0] == target;
            }
            int l = 0, r = n-1;
            while(l <= r){
        
                int mid = l + (r - l) / 2;
                if(nums[mid] == target) return true;
                if(nums[mid] > nums[r]){
         // mid位于前面递增序列
                    if(nums[l]<=target && target < nums[mid]){
        
                        r = mid-1;
                    }else{
        
                        l = mid+1;
                    }
                }else if(nums[mid] < nums[r]){
         // mid位于后面递增序列
                    if(nums[mid] < target && target <= nums[r]){
        
                        l = mid+1;
                    }else{
        
                        r = mid-1;
                    }
                }else{
        
                    r--;
                }
            }
            return false;
        }
    };

--------------------

# 其他 #

## [162. 寻找峰值][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。

class Solution {
        
    public:
        int findPeakElement(vector<int>& nums) {
        
            int l = 0, r = nums.size()-1;
            while(l < r){
        
                int mid = l + (r - l)/2;
                if(nums[mid] > nums[mid+1]){
        
                    r = mid;
                }else{
        
                    l = mid + 1;
                }
            }
            return r;
        }
    };

## [4. 寻找两个正序数组的中位数][4.] ##

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

> 输入：nums1 = \[1,3\], nums2 = \[2\]  
> 输出：2.00000  
> 解释：合并数组 = \[1,2,3\] ，中位数 2

示例 2：

> 输入：nums1 = \[1,2\], nums2 = \[3,4\]  
> 输出：2.50000  
> 解释：合并数组 = \[1,2,3,4\] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

> 输入：nums1 = \[0,0\], nums2 = \[0,0\]  
> 输出：0.00000

### 暴力 ###

合并两数组，然后重排序取中位数 O((m+n)log(m+n))

### 归并排序 ###

就是对两个有序数组进行合并得到新的一个有序数组，O((m+n))

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
      // 归并排序合并再取中位数O(m+n)
           float newNums[2005] = {
        0};
           int k = 0;
           int l1 = 0, l2 = 0;
           while(l1 < nums1.size() && l2 < nums2.size()){
        
               if(nums1[l1] < nums2[l2]){
        
                   newNums[k++] = nums1[l1];
                   l1++;
               }
               else{
        
                   newNums[k++] = nums2[l2];
                   l2++;
               }
           }
           while(l1 < nums1.size()){
        
               newNums[k++] = nums1[l1];
               l1++;
           }
           while(l2 < nums2.size()){
        
               newNums[k++] = nums2[l2];
               l2++;
           }
           if(k % 2 == 0){
        
               return (newNums[k/2-1]+newNums[k/2]) / 2;
           }else{
        
               return newNums[k/2];
           }
    }

### 二分划分数组（最优） ###

我们希望使用一条红色分割线将两个数组分割成两部分，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]  
要求是：

*  如果两个数组元素总数为偶数，那么这个红色分割线分割的两部分元素个数相等；如果两个数组元素总数为奇数，那么这个红色分割线分割的左半部分元素个数比右半部分元素个数多1（人为规定）。
 *  红色分割线左边的所有元素数值 <= 右边的所有元素的数值

这样中位数只与红色分割线两侧元素有关。

具体看代码：

class Solution {
        
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
            if(nums1.size() > nums2.size()){
        
               return findMedianSortedArrays(nums2, nums1);
            }
            int m = nums1.size(), n = nums2.size(); // 两个数组的长度
            int totalLeft = (m+n+1)/2; // 红色分割线左半部分元素个数
            int left = 0, right = m; // 只需要找到nums1的分割位置i，就确定了nums2的分割位置j
            while(left < right){
        
                int i = left + (right - left + 1) / 2;
                int j = totalLeft - i;
                if(nums1[i-1] > nums2[j]){
        
                	// 左半部元素大于交叉的右半部元素，所以需要缩小右范围，下一轮搜索的区间 [left, i - 1]
                    right = i - 1;
                }else{
        
                	// 缩小左范围，下一轮搜索的区间 [i, right]
                    left = i;
                }
            }
            int i = left, j = totalLeft-i;
            // 需要考虑边界条件。
            int nums1LeftMax = i == 0 ? INT_MIN:nums1[i-1];
            int nums1RightMin = i == m ? INT_MAX:nums1[i];
            int nums2LeftMax = j == 0 ? INT_MIN:nums2[j-1];
            int nums2RightMin = j == n ? INT_MAX:nums2[j];
    
            if((m+n)%2==1){
        
                return max(nums1LeftMax, nums2LeftMax);
            }else{
        
                return ((double)max(nums1LeftMax, nums2LeftMax) + (double)min(nums1RightMin, nums2RightMin)) / 2;
            }
        }
    };

时间复杂度：**O(log(min(M, N)))**

[704.]: https://leetcode-cn.com/problems/binary-search/
[34.]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[278.]: https://leetcode-cn.com/problems/first-bad-version/
[153.]: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
[154. _ II]: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
[Link 1]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
[81._ II]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
[162.]: https://leetcode-cn.com/problems/find-peak-element/
[4.]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]: /images/20221014/efe8339c6a2846ec9448f2196b41a1ba.png