35.搜索插入位置

https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-liked
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

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

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

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

时间：O（logn）空间O(1)

关于为何最终返回left作为插入位置：

这里面存在循环不变量：证明类似数学归纳法，证明初始成立，证明循环任意一次结束成立，终止时自然成立（只要循环成立）

任何时候left左侧的元素都小于target
任何时候right右侧的元素都大于target

因为，在开始时，left左侧right右侧都无元素，可以认为真；

循环中间，情况A nums[mid] < target,left更新为mid+1，left左侧依然都小于target

同理right任何时候右侧都大于target

所以任意一次结束都满足。

结束时，left>right，并且left左侧都小于target，right右侧都大于target

所以target插入的话，它的索引就应当是left

74.搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

最简单的想法就是每行依次二分查找。时间复杂度O(mlogn)

也可以直接把矩阵化成大数组，时间复杂度O(logm + logN)

进一步，直接先对行数进行二分查找，再对选定的行进行二分查找

up = 0,down = m,mid =(up+down)/2,判断是否在这一行。

比较matrix[mid][0]和matrix[mid][n-1]根据需要移动up或者down。

之后对选定的行进行二分查找

时间复杂度也是O(logm + logn)，但是空间复杂度降低到O(1)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int up = 0;
        int down = matrix.length - 1;
        int result = -1;
        int m = matrix.length;
        int n = matrix[0].length;
        while (up <= down){
            int mid = up + (down - up ) / 2;
            if (target >= matrix[mid][0] && target <= matrix[mid][n-1]){
                result = mid;
                break;
            } else if (target < matrix[mid][0]) {
                down = mid - 1;
            }else if (target > matrix[mid][n-1]){
                up = mid + 1;
            }
        }
        if (result == -1){
            return false;
        }
        int left = 0;
        int right = n - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (matrix[result][mid] == target){
                return true;
            } else if (matrix[result][mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return false;
    }
}

事实上，关于把整个矩阵看成一维数组的方法，也可以把空间复杂度从O(MN)降低到O(1),使用映射，把行列坐标映射到一维

使用公式 l = row*n+col ,row属于[0,m-1],col属于[0,n-1]

所以L范围是[0,mn-1]

已知l怎么推出row和col呢

row = l / n

col = l % n

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m*n-1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            int row = mid / n;
            int col = mid % n;
            if (matrix[row][col] == target){
                return true;
            } else if (matrix[row][col] < target) {
                left = mid + 1;
            } else if (matrix[row][col] > target) {
                right = mid - 1;
            }
        }
        return false;
    }
}

还有个Z字搜索法，时间复杂度O(M+N)

这是一种非常巧妙且直观的算法，它充分利用了矩阵的两个有序属性，但思路与二分查找完全不同。

核心思想

Z字形搜索法的核心思想是：通过每一步比较，都能排除掉一整行或一整列的元素，从而不断缩小搜索范围，直到找到目标值或搜索空间为空。

为了实现“排除一行或一列”的效果，我们必须从一个特殊的“拐角”开始。这个拐角需要满足一个条件：从这个位置出发，移动到相邻位置时，一个方向的元素值会变大，而另一个方向的元素值会变小。

在满足题目条件的矩阵中，只有两个点符合要求：

右上角 (matrix[0][n-1])：
- 向下移动，值会变大。
- 向左移动，值会变小。
左下角 (matrix[m-1][0])：
- 向上移动，值会变小。
- 向右移动，值会变大。

为什么不能从左上角或右下角开始？

从左上角 (matrix[0][0]) 开始，向右和向下移动，值都会变大。如果 target 大于当前值，我们无法决定是向右还是向下，因为两个方向都有可能。
同理，从右下角 (matrix[m-1][n-1]) 开始，向左和向上移动，值都会变小，也无法做出唯一决策。

算法步骤 (以右上角为例)

我们以从右上角开始搜索为例，这是最常见的实现方式。

初始化：

设置一个指针，初始位置在矩阵的右上角。
row = 0
col = n - 1 (n是列数)

循环搜索：
在指针没有越出矩阵边界 (row < m 且 col >= 0) 的情况下，循环执行以下步骤：

获取当前指针位置的元素值 current = matrix[row][col]。
将 current 与 target 进行比较：
- 情况一：current == target
  - 找到了！直接返回 true。
- 情况二：current > target
  - 这意味着当前值太大了。因为当前列 (col) 中位于当前位置下方的所有元素都比 current 更大，所以它们也一定都大于 target。因此，我们可以排除当前这一整列。
  - 操作： 将指针向左移动一位，col--。
- 情况三：current < target
  - 这意味着当前值太小了。因为当前行 (row) 中位于当前位置左边的所有元素都比 current 更小，所以它们也一定都小于 target。因此，我们可以排除当前这一整行。
  - 操作： 将指针向下移动一位，row++。
如果循环结束（指针越界），说明搜索空间已经为空，但仍未找到目标值。返回 false。

复杂度分析

时间复杂度：O(m + n)
- 指针 row 从 0 开始，最多增加到 m（向下移动 m 次）。
- 指针 col 从 n-1 开始，最多减少到 -1（向左移动 n 次）。
- 每一步，row 或 col 都会移动，且方向是固定的（row 只增不减，col 只减不增）。因此，总的移动步数最多为 m + n。
空间复杂度：O(1)
- 该算法只需要常数个变量（row, col）来存储指针位置，不需要任何额外的存储空间。

与二分查找的对比

特性	Z字形搜索法	二分查找法
时间复杂度	O(m + n)	O(log m + log n)
代码实现	通常更简单、更直观	稍微复杂，需要处理索引映射或两次搜索
性能	当 m 或 n 较小时表现优异	当 m 和 n 都很大时，对数复杂度更具优势
适用性	适用于本题这种行列均有序的矩阵	适用于本题，且更通用（只要能虚拟化为一维有序数组即可）

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

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
给你一个按照非递减顺序排列的整数数组 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]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

非递减顺序就是不严格递增的意思

二分查找可以在O(logn)时间找到一个目标元素

循环不变量：

left左侧的都小于目标，right右侧的大于目标元素。

终止时，

不存在
存在，mid指向一个目标元素，left左侧都小于目标，right右侧都大于目标

对于存在的情况，left左侧和right右侧都确定了不是mid，因此只要再比较一下left和right。

对于left

如果left = 目标，可以确定至少[left,mid]是目标区间；
如果left < 目标，left指针依次右移直到left = 目标（如果mid左侧没有目标那么left会移到mid）
left 不可能大于目标

对于right同理

复杂度：
查询到第一个目标元素耗时O(logn),确定区间O(n)复杂度不可以
能不能在[left,mid]继续二分查找？但是不能确定目标区间的左端点？要查询直到不存在目标元素吗？还是无法确定左边界

实际上可以的，但是需要对传统的二分查找改造

查找左边界

如果nums[mid] < target,那么left = mid + 1

如果nums[mid] >= target,那么right = mid - 1，并且使用ans记录此时的mid。ans表示的是，它的以及它的右边必定大于等于target。最终目标是找到最左侧的这个ans，它以及右侧都大于等于target，但是，左侧都小于target

之后判断一下nums[ans]是否等于target即可

查找右边界

也是查找一个ans，使它的左边都小于等于target，右边都大于target

如果nums[mid] > target,right = mid - 1;

如果nums[mid] <= target,left = mid + 1,并记录此时的mid为ans

判断nums[ans]是否等于target

具体实现时，只实现一个查找第一个大于等于目标元素的索引的方法即可。

这个索引要么是左边界，要么是要插入的地方

查找target，记录左边界；

查找target + 1，得到的索引减一即可

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ans = searchInsert(nums,target);
        if (ans > nums.length-1 || nums[ans] != target){
            return new int[]{-1,-1};
        }
        int right = searchInsert(nums,target + 1) - 1;
        return new int[]{ans,right};
    }
    private int searchInsert(int[] nums,int target){//找到第一个大于等于target的位置，也就是最左边的大于等于target的位置,也是如果不在要插入的位置
        int left = 0;
        int right = nums.length - 1;
        int ans = nums.length;//初始化为数组长度，这样能处理如果所有元素都小的情况，插在末尾
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                left = mid + 1;
            }else {//nums[mid]>=target
                ans = mid;
                right = mid - 1;
            }
        }
        return ans;
    }
}

注意，Java的局部遍历必须显示初始化，只有成员变量可以不显示初始化。

33.搜索旋转排序数组

https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
整数数组 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 。

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

示例 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

提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

必定存在一个点，这个分界点（也就是原数组的最大值）以及左侧有序，右侧有序。

二分，mid的左边和右边必定至少有一边有序。因为mid只能在分界点左侧或者右侧或者就是分界点。

如果nums[left] < nums[mid]说明左边有序。（分界点左侧是整个数组相对大的一部分，假设左侧无序，说明分界点在左侧，因此分界点左侧的数应当都大于分界点右侧，矛盾）

判断target是否在[left,mid]，在的话执行二分，不在的话让left = mid+1

如果右边有序同样

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[left] <= nums[mid]){//注意无重复，因此相等只可能在单元素时出现，单元素应当认为有序
                if (nums[left] <= target && target <= nums[mid]){
                    return bySearch(nums,left,mid,target);
                }else {
                    left = mid + 1;
                }
            }else {
                //nums[mid]<nums[right],右侧有序
                if (nums[mid] <= target && target <= nums[right]){
                    return bySearch(nums,mid,right,target);
                }else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
    private int bySearch(int[] nums,int left,int right,int target){
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return -1;
    }

}

上面实现可以更简洁

不需要bySearch函数

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            
            if (nums[left] <= nums[mid]) { 
                // 如果左半部分是有序的
                // 判断 target 是否在左半部分的范围内
                if (nums[left] <= target && target < nums[mid]) {
                    // 目标在左侧有序区间，缩小范围到左侧，后续肯定左侧都是有序的，只会执行左侧有序的if分支
                    right = mid - 1;
                } else {
                    // 目标不在左侧，去右侧查找
                    left = mid + 1;
                }
            } else { 
                // 如果左半部分是无序的，那么右半部分 [mid, right] 必定是有序的
                // 判断 target 是否在右半部分的范围内
                if (nums[mid] < target && target <= nums[right]) {
                    // 目标在右侧有序区间，缩小范围到右侧，以后只会执行右侧的if分支
                    left = mid + 1;
                } else {
                    // 目标不在右侧，去左侧查找
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
}

每次范围缩小一半，因此是O(logn)

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

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
已知一个长度为 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 次得到输入数组。

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

感觉和上一题搜索旋转排序数组很像

存在一个断点，它以及左侧是是单调递增的，它的右侧是也是单调递增的

二分后这个断点必然存在在mid左侧或者右侧或者就是mid

最小的数就是mid + 1指向的

关键在于查找mid

每次把无序的部分继续查找，直到left 和right相邻，这两个较大的就是mid

但要注意如果数组本来就是有序的（也就是说left指向的小于等于mid小于等于right），那么直接返回nums[0]

class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        if (nums.length == 2){
            return Math.min(nums[0],nums[1]);
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right - 1){
            int mid = left + (right - left) / 2;
            if (nums[left] <= nums[mid] && nums[mid] <= nums[right]){
                return nums[0];//数组整体有序
            }
            if (nums[left] <= nums[mid] ){
                //左侧有序,查找右侧
                left = mid;
            }
            if (nums[mid] <= nums[right]){
                right = mid;
            }
        }
        int max = -1;
        if (nums[left] > nums[right]){
            max = left;
        }else {
            max = right;
        }
        return nums[max+1];
    }
}

时间复杂度:O(logn),空间O(1).

上面可以优化，代码逻辑分支复杂

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        // 循环条件：当 left 和 right 相遇时，就找到了最小值（循环不变量：最小值必定在[left,right]之间
        while (left < right) {
            int mid = left + (right - left) / 2;

            // 情况1: mid 在右侧的、值较小的递增序列上
            // 此时，最小值可能是 mid 本身，或者在 mid 的左侧
            // 所以，我们将搜索范围缩小到 [left, mid]
            if (nums[mid] < nums[right]) {
                right = mid;
            } 
            // 情况2: mid 在左侧的、值较大的递增序列上
            // 此时，最小值一定在 mid 的右侧
            // 所以，我们将搜索范围缩小到 [mid + 1, right]
            else {
                left = mid + 1;
            }
        }
        
        // 循环结束时，left 和 right 指向同一个位置，即为最小值
        return nums[left];
    }
}

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

https://leetcode.cn/problems/median-of-two-sorted-arrays/description/?envType=study-plan-v2&envId=top-100-liked
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

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

示例 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

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

根据中位数的定义，当 m+n 是奇数时，中位数是两个有序数组中的第 (m+n)/2 个元素，

当 m+n 是偶数时，中位数是两个有序数组中的第 (m+n)/2 个元素和第 (m+n)/2+1 个元素的平均值。

因此，这道题可以转化成寻找两个有序数组中的第 k 小的数，其中 k 为 (m+n)/2 或 (m+n)/2+1。

可以通过比较A[k/2 - 1],和B[k/2 - 1]

A[k/2 -1]<B[k/2 - 1]:则最多有k/2 - 1 + k/2-1 = k-2个元素小于A[k/2 - 1],也就是A[k/2-1]最多是第k-1个元素，因此可以排除A[k/2-1]以及左侧的所有元素
A[k/2 - 1]>B[k/2-1]:同上，排除B
A[k/2 - 1]==B[k/2 - 1]:排除任意一个就行。也只能排除一个。我们排除A。因为还是最多k/2 -1 + k/2 - 1 = k-2元素小于A[k/2 - 1],因此A[k/2 - 1]最多是第k-1个，可以排除A[k/2 - 1]以及左侧。但是不能同上排除B[k/2 - 1],因为B可能就是第k个了

更新k直到1

边界：

k/2-1越界，则选取对应数组的最后一个元素。但这种情况，更新k必须依照实际减少的元素
如果任意一个数组为空，说明此数组以及排除完，直接返回另一个数组的第k个
如果k=1，返回两个数组中中较小的一个

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if ((m + n) % 2 == 0){
            int k1 = (m+n)/2 ;
            int k2 = (m+n)/2 + 1;
            return (getKthEtem(nums1,nums2,k1) + getKthEtem(nums1,nums2,k2))/2.0;
        }else {
            int k = (m + n) / 2 + 1;
            return (double) getKthEtem(nums1,nums2,k);
        }
    }
    private int getKthEtem(int[] nums1,int[] nums2,int k){//得到的是第1，2……个
        int length1 = nums1.length;
        int length2 = nums2.length;
        int index1 = 0;
        int index2 = 0;
        while (true){
            if (index1 == nums1.length){
                return nums2[index2 + k-1];
            }
            if (index2 == nums2.length){
                return nums1[index1 + k-1];
            }
            if (k == 1){
                return Math.min(nums1[index1],nums2[index2]);
            }
            
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half,length1) - 1;
            int newIndex2 = Math.min(index2 + half,length2) - 1;
            if (nums1[newIndex1] <= nums2[newIndex2]){
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }
}

时间复杂度O(logk),因为k是m+n的线性倍数，所以最终就是O(log(m+n)),并且空间复杂度O(1)

方法二

中位数实际上就是：

将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

      left_part          |         right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

可以这样进行划分，在A找一个len(leftA) = i,B找一个len(leftB) = j,则len(left_part) = i + j

len(right_part) = m+n-i-j.

当m+n是偶数：要满足len(left_part)=len(right_part),可以解得i+j = (m+n)/2，Max(left_part)<=Min(right_part)中位数是（Max(left_part)+Max（right_part))/2

奇数：len(left_part) = len(right_part) + 1,可解得i+j=(m+n+1)/2,Max(left_part)<=Min(right_part),中位数是Max(left_part)

i和j得约束条件可以统一为可以统一为i+j = (m+n+1) / 2

最大值条件实际上就是A[i-1] <= B[j],B[j-1]<=A[i]

为了简便分析，我们可以认为A[i-1],B[i-1]始终存在，即认为A[-1]B[-1]是无穷小，A[length]B[length]为无穷大

因此，我们要做的实际上就是

在 [0,m] 中找到 i，使得： B[j−1]≤A[i] 且 A[i−1]≤B[j]，其中 j=(m+n+1)/2.(不妨假设m<n)

实际上这个等价于：

在 [0,m] 中找到最大的 i，使得： A[i−1]≤B[j]，其中 j=(m+n+1)/2
（因为，既然i是最大的，那么i+1肯定不满足这个条件，于是A[i]>B[j-1])

所以我们得目标就是查找这个i

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int m = nums1.length;
        int n = nums2.length;//m<n
        int left = 0;
        int right = m;//这里应该是m，i的含义是左边取几个数，可以取[0,m]个数
        int i = -1;
        while (left <= right){//循环不变量：如果还有更右侧的mid存在的话，那么它一定在[left,right]中
            int mid = left + (right - left) / 2;
            int j = (m + n + 1) / 2 - mid;
            int nums_im1 = mid - 1 >= 0 ? nums1[mid - 1] : Integer.MIN_VALUE;
            int nums_j = j < n ? nums2[j] : Integer.MAX_VALUE;
            if (nums_im1 <= nums_j){
                i = mid;
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        int j = (m+n+1)/2 - i;
        int nums_im1 = i-1 >= 0 ? nums1[i-1] : Integer.MIN_VALUE;
        int nums_jm1 = j-1 >= 0 ? nums2[j-1] : Integer.MIN_VALUE;
        int nums_i = i<m ? nums1[i] : Integer.MAX_VALUE;
        int nums_j = j<n ? nums2[j] : Integer.MAX_VALUE;
        if ((m + n) % 2 == 0){
            //偶数
            int maxLeft = Math.max(nums_im1,nums_jm1);
            int minRight = Math.min(nums_i,nums_j);
            return (maxLeft + minRight) / 2.0;
        }else {
            return Math.max(nums_im1,nums_jm1);
        }

    }
}

时间复杂度O(log(min(m,n)))

空间复杂度O(1)