03 二分查找 局部有序

​ 我们已经知道二分查找是一种在有序数组中查找某一特定元素的查找算法。

​ 那如果一个数组不是整体有序，而是局部有序呢？这时我们就可以通过分治策略，我们在局部有序的区间内进行二分查找，然后合并各个局部结果组成整体结果。

153 寻找旋转排序数组中的最小值 (opens new window)

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。

输入一个元素互不相同的数组，输出一个整型值表示数组的最小值。

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

解析：

​ 一个不包含重复元素的升序数组在经过旋转之后，我们可以直接将其划分为两个部分，例如数组[4,5,6,7,0,1,2]可以划分为[4,5,6,7] 和 [0,1,2]两个部分。可以看出数组的最小值就是旋转数组两个局部有序区间的分界点。

​ 那我们怎么找到这个分界点呢？因为数组在旋转之前是整体有序的，所以旋转之后nums[0]是进行旋转的中心，那么旋转之后数组局部有序的两个部分中一部分中的元素全都大于等于nums[0]，另一部分中的元素全都小于nums[0]。

利用这一特性，我们使用二分查找的方法找到旋转数组这两部分的分界点：

• 从中间开始找，如果当前查找的值大于等于nums[0]，那么分界点在 mid 的右侧 left = mid+1
• 如果当前查找的值小于nums[0]，那么分界点在 mid 的左侧 right = mid
• 循环上述步骤最终找到分界点 left == right

​ 当然我们要考虑到一个特殊情况：长度问n的数组旋转了n恢复到原来的状态。这种情况下我们不能用上述寻找分界点的方式去找最小值，因为该情况不能将旋转数组划分为大于等于nums[0]局部有序区间 + 全都小于nums[0]局部有序区间的两部分组合。但是这种情况的最小值也很好找就是nums[0]，且很容易判断这种情况就是数组首元素小于尾元素，说明该数组整体有序。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size();
        // nums[left] < nums[right-1] 判断数组是否是整体有序
        // nums[left] == nums[right-1] 判断数组是否只有一个元素
        if(nums[left]<=nums[right-1]){
            return nums[left];
        }
        // 二分查找寻找分界即最小值
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] < nums[0]){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return nums[left];
    }
};

154 寻找旋转排序数组中的最小值 II (opens new window)

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。

输入一个可能存在重复元素的数组，输出一个整型值表示数组的最小值。

输入：nums = [2,2,2,0,1,2]
输出：0

解析：

​ 本题和153 寻找旋转排序数组中的最小值 (opens new window)解决方法一样，唯一的区别是我们需要考虑元素重复的情况。

​ 旋转情况我们还是通过寻找分界点来找数组中的最小值，还是根据旋转数组的特性以nums[0]作为参考值将数组划分为大于等于nums[0]和小于nums[0]的两部分。

​ 但是如果存在重复的元素，这种二分类的划分将无法实现。例如[2,3,0,1,2,2,2,2,2]，我们将其划分为[2,3]和[0,1,2,2,2,2,2]，显然[0,1,2,2,2,2,2]并不满足全都小于nums[0]==2的条件。这种情况下我们无法正确地使用二分查找寻找分界点，例如上例中第一次循环中 nums[mid] == nums[4] == 2，这将导致向其右侧寻找分界点，显然那无法找到。

​ 那么我们怎么让存在重复元素的旋转数组恢复可二分类的特性呢？

​ 可以观察到只有当以重复元素为旋转中心时才会破坏旋转数组的可二分类特性。恢复方法也很简单，只需要删除小于nums[0]局部区间中的等于nums[0]的元素即可，即将旋转数组尾部与nums[0]相等的元素删除即可。这种操作并不会影响对数组整体最小值的判断，也恢复了旋转数组的可二分类特性。

class Solution {
public:
    int findMin(vector<int>& nums) {
        // 删除旋转数组尾部与nums[0]相等的元素，tail>0 如果数组元素全都一样要保留nums[0]
        int tail = nums.size()-1;
        while(tail>0){
            if(nums[tail]==nums[0]){
                --tail;
            }else{
                break;
            }
        }
		
        // nums[left] < nums[right-1] 判断数组是否是整体有序
        // nums[left] == nums[right-1] 判断数组是否只有一个元素	
        int left = 0, right = tail+1;
        if(nums[left]<=nums[right-1]){
            return nums[left];
        }
        // 二分查找寻找分界即最小值
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] < nums[0]){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return nums[left];
    }
};

33 搜索旋转排序数组 (opens new window)

一个原本增序的数组被首尾相连后按某个位置断开（如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]，在第4位断开），我们称其为旋转数组。给定一个值，判断这个值是否存在于这个为旋转数组中。

输入是一个数组和一个值，输出是一个整型值，表示目标值在旋转数组中的位置，若不存在则返回 -1。

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

解析：

​ 我们观察这个所谓的旋转数组可以看到数组[4,5,6,7,0,1,2]可以划分为有序的两个部分，分别为[4,5,6,7] 和 [0,1,2]。所以我们可以在这两个局部有序的部分中使用二分查找搜索目标值。

​ 基于上述思路我们需要完成两个任务：

• 找到划分局部有序的分界点
• 使用二分查找在局部有序的数组中搜索目标值

​ 第一个任务我们可以利用旋转数组的特性快速找到分界点。旋转数组中两个局部有序的部分可以用一个简单的性质划分：因为数组在旋转之前是整体有序的，所以旋转之后nums[0]是进行旋转的中心，那么旋转之后数组局部有序的两个部分中一部分中的元素全都大于等于nums[0]，另一部分中的元素全都小于nums[0]。

​ 利用这一特性，我们使用二分查找的方法找到旋转数组这两部分的分界点：

• 从中间开始找，如果当前查找的值大于等于nums[0]，那么分界点在 mid 的右侧 left = mid+1
• 如果当前查找的值小于nums[0]，那么分界点在 mid 的左侧 right = mid
• 循环上述步骤最终找到分界点 left == right

​ 第二个任务我们仍然可以基于旋转数组的特性，直接将目标值 target 与 nums[0] 比较选择对应的局部有序区间中进行二分查找。

​ 当然也可以使用分治策略，不进行比较而是直接根据分界点划分的两个区间，同时在两个区间中使用二分查找搜索目标值 target，返回由多个局部结果组成的最终结果。

class Solution {
public:
    int binarySerach(vector<int> nums, int target, int leftBound, int rightBound){
        int left = leftBound, right = rightBound;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }

    int search(vector<int>& nums, int target) {
        // 使用二分查找找到分界点，将数组分为大于等于nums[0]的和小于nums[0]的两部分
        int left = 0, right = nums.size();
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] < nums[0]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
		// 如果目标值小于nums[0]，则在分界点右侧的局部有序区间中用二分查找搜索目标值
        if(nums[0] > target){
            return binarySerach(nums,target,left,nums.size());
        }else{
            // 如果目标值大于等于nums[0]，则在分界点左侧的局部有序区间中用二分查找搜索目标值
            return binarySerach(nums,target,0,left);
        }
    }
};

81 搜索旋转排序数组 II (opens new window)

一个存在重复元素且原本增序的数组被首尾相连后按某个位置断开（如 [0,0,1,2,2,5,6] → [2,5,6,0,0,1,2]，在第4位断开），我们称其为旋转数组。给定一个值，判断这个值是否存在于这个为旋转数组中。

输入是一个数组和一个值，输出是一个布尔值，表示数组中是否存在该值。

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

解析：

​ 本题和33 搜索旋转排序数组 (opens new window)解决方法一样，唯一的区别是我们需要考虑元素重复的情况。

​ 同样，我们可以通过找分界点将旋转数组划分为两个局部有序的部分，并在局部有序的区间中使用二分查找搜索目标值。我们仍然需要完成两个任务：

• 找到划分局部有序的分界点
• 使用二分查找在局部有序的数组中搜索目标值

​ 寻找分界点我们还是根据旋转数组的特性以nums[0]作为参考值将数组划分为大于等于nums[0]和小于nums[0]的两部分。

​ 但是如果存在重复的元素，这种二分类的划分将无法实现。例如[2,5,6,0,0,1,2]，我们将其划分为[2,5,6]和[0,0,1,2]，显然[0,0,1,2]并不满足全都小于nums[0]==2的条件。

​ 那么我们怎么让存在重复元素的旋转数组恢复可二分类的特性呢？

​ 可以观察到只有当以重复元素为旋转中心时才会破坏旋转数组的可二分类特性。恢复方法也很简单，只需要删除小于nums[0]局部区间中的等于nums[0]的元素即可，即将旋转数组尾部与nums[0]相等的元素删除即可。这种操作并不会影响对元素存在性的判断，也恢复了旋转数组的可二分类特性。

​ 解决了重复元素的问题，其他的步骤就和33 搜索旋转排序数组 (opens new window)解决方法一致了。

class Solution {
public:
    bool  binarySearch(vector<int> nums, int target, int leftBound, int rightBound){
        int left = leftBound, right = rightBound;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                return true;
            }else if(nums[mid] > target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return false;
    }

    bool search(vector<int>& nums, int target) {
        // 删除旋转数组尾部与nums[0]相等的元素，tail>0 如果数组元素全都一样要保留nums[0]
        int tail = nums.size()-1;
        while(tail>0){
            if(nums[tail]==nums[0]){
                --tail;
            }else{
                break;
            }
        }
        
        // 使用二分查找找到分界点，将数组分为大于等于nums[0]的和小于nums[0]的两部分
        int left = 0, right = tail+1;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] < nums[0]){
                right = mid;
            }else{
                left = mid+1;
            }
        }
		
        // 如果目标值小于nums[0]，则在分界点右侧的局部有序区间中用二分查找搜索目标值
        if(nums[0] > target){
            return binarySearch(nums,target,left,nums.size());
        }else{
            // 如果目标值大于等于nums[0]，则在分界点左侧的局部有序区间中用二分查找搜索目标值
            return binarySearch(nums,target,0,left);
        }
    }
};

4 寻找两个正序数组的中位数 (opens new window)

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

输入两个有序数组，输出一个浮点型值表示两个数组的中位数，要求算法的时间复杂度应该为 O(log (m+n))。

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

解析：

​ 本题没有完全理解，有待更新

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }

    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
        if (k == 1) {
            if (nums1.size() == i) return nums2[j];
            else return min(nums1[i], nums2[j]);
        }
        if (nums1.size() == i) return nums2[j + k - 1];
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
            return find(nums1, i, nums2, sj, k - (sj - j));
        else
            return find(nums1, si, nums2, j, k - (si - i));
    }
};