二分

注意点

while中的条件是(循环终止)的条件，也就是说搜索区间为空的应该停止
if(),else if()两个条件要分到两个属性当中
left=mid+1,right=right-1还是right=mid,left=mid，按照上面的条件，尽可能逼近目标位置

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

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

算法的时间复杂度应该为 O(log (m+n)) 。

朴素解法

如果忽略进阶的 O(log(m+n)) 要求，这道题就非常简单。

一个比较直观的做法：将两个数组合并，排序，然后分别取得 total / 2 和 (total - 1) / 2 两个位置的数，取两者平均值。

时间复杂度：合并两个数组的复杂度是 O(m+n)，对合并数组进行排序的复杂度是 O((m+n)log(m+n))。整体复杂度是 O((m+n)log(m+n)) 空间复杂度：O(1)

解答：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        boolean isOdd = (m + n) % 2 == 1;
        if(isOdd){
            return getKth(nums1, 0, nums2, 0, (m + n) / 2 + 1);
        } else {
            int first = getKth(nums1, 0, nums2, 0, (m + n) / 2);
            int second = getKth(nums1, 0, nums2, 0, (m + n) / 2 + 1);
            return (double)(first + second) / 2;
        }

    }
    private int getKth(int[] nums1, int i, int[] nums2, int j, int k){ // i, j are the start indices of nums1 and nums2 respectively, k is the kth element.
        if(nums1.length - i > nums2.length - j){ // if nums1 has more elements, then we need to swap nums1 and nums2.
            return getKth(nums2, j, nums1, i, k);
        }
        if(i >= nums1.length) return nums2[j + k - 1];

        if(k == 1) return Math.min(nums1[i], nums2[j]);
        else{
            int si = Math.min((i + k / 2 - 1), (nums1.length - 1));
            int sj = k - (si - i + 1) + (j - 1);
            if(nums1[si] > nums2[sj]){ // the kth element isn't in nums2[j, sj]
                return getKth(nums1, i, nums2, sj + 1, k - (sj - j + 1));
            } else if(nums1[si] < nums2[sj]){ // the kth element isn't in nums1[i, si]
                return getKth(nums1, si + 1, nums2, j, k - (si - i + 1));
            } else {
                return nums1[si];
            }
        }
    }
}

在传递给函数之前，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 。

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

解答：

// 朴素解法
class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 1) return nums[0] == target ? 0 : -1;
        int left = 0, right = nums.length - 1;
        int high = left + (right - left) / 2;
        
        int low = 0;
        if(nums[right] > nums[left]){ // 先找到分割点
            high = right;
            low = left;
        }
        else{
            while(nums[high] < nums[left]) high--;
            low = high+1;
            while(nums[low] > nums[right]) low++;
            high = low-1;
        }
        

        if(target >= nums[left]){ // 再实施二分
            while(left <= high){
                int mid = left + (high - left) / 2;
                if(nums[mid] == target) return mid;
                else if(nums[mid] < target) left = mid + 1;
                else high = mid - 1;
            }
        }
        else{
            while(low <= right){

                int mid = low + (right - low) / 2;
                if(nums[mid] == target) return mid;
                else if(nums[mid] > target) right = mid - 1;
                else low = mid + 1;
            }
        }
        return -1;
    }
}

二分解法不难发现，虽然在朴素解法中我们应用了「二分」查找。

但理论复杂度为 O(n)，实际复杂度也远达不到 O(logn)，执行效率取决于旋转点 idx 所在数组的下标位置。

那么我们如何实现 O(logn) 的解法呢？

这道题其实是要我们明确「二分」的本质是什么。

「二分」不是单纯指从有序数组中快速找某个数，这只是「二分」的一个应用。

「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。

经过旋转的数组，显然前半段满足 >= nums[0]，而后半段不满足 >= nums[0]。我们可以以此作为依据，通过「二分」找到旋转点。

解答：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(n == 0) return -1;
        if(n == 1) return nums[0] == target ? 0 : -1;
        int left = 0, right = n;
        while(left < right){ // find the lowest index of the rotated array
            int mid = left + ((right-left) >> 1);
            if(nums[0] > nums[mid]){
                right = mid;
            } else{
                left = mid + 1;
            }
        }

        if(nums[0] <= target){
            left = 0;
            right--;
        }else{
            right = n-1;
        }

        while(left <= right){
            int mid = left + ((right-left) >> 1);
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        
        return -1;
    }
}

未完待续~~~

注意点​

4. 寻找两个正序数组的中位数​

33. 搜索旋转排序数组​

注意点

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

33. 搜索旋转排序数组