【算法二十】 114. 寻找两个正序数组的中位数 153. 寻找旋转排序数组中的最小值
114. 寻找两个正序数组的中位数
一个二分：
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; if(m > n){ return findMedianSortedArrays(nums2,nums1); } int iMin = 0, iMax = m; while(iMin <= iMax){ int i = iMin + (iMax - iMin)/2; int j = (m + n + 1)/2 - i; //左上大于右下,i大了,i左移 if(i!=0 && j!=n && nums1[i-1] > nums2[j]){ iMax = i-1; } //左下大于右上,i小了,i右移 else if(i!=m && j!=0 && nums2[j-1] > nums1[i]){ iMin = i+1; } //调好i和j了 else{ //求左侧最大值 int leftMax = 0; //上面左侧没有数时 if(i==0){ leftMax = nums2[j-1]; } //下面左侧没有数时 else if(j==0){ leftMax = nums1[i-1]; } //上下都有数，就要比较了 else{ leftMax = Math.max(nums1[i-1],nums2[j-1]); } //若两个数组长度和为奇数，那中位数就是左侧最大数，因为奇数，左侧会多一个数 if((m + n) % 2!=0){ return leftMax; } //偶数就要求右侧最小值，求平均值了 else{ int rightMin = 0; //i==m时 if(i==m){ rightMin = nums2[j]; } //j==n时 else if(j==n){ rightMin = nums1[i]; } else{ rightMin = Math.min(nums1[i],nums2[j]); } return (leftMax+(rightMin - leftMax)/2.0); } } } return 0.0; } }时间复杂度：O(log(min(m,n)))
空间复杂度：O(1)
核心：通过分割线将两个数组分为左右两边相似的数量，找规律得到m+n与i和j的关系，所以只要二分出一个i，就可以得到j，通过分析几种情况得到结果
153. 寻找旋转排序数组中的最小值
二分：
class Solution { public int findMin(int[] nums) { int n = nums.length; int left = 0; int right = n - 2; // 右闭：因为我们要和最后一个数 nums[n-1] 比较，搜索范围是 [0, n-2] while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] >= nums[n - 1]) { // 如果当前值大于最后一个值，说明最小值在 mid 右侧 // 搜索区间变为 [mid + 1, right] left = mid + 1; } else { // 如果当前值小于最后一个值，说明最小值在 mid 或 mid 左侧 // 搜索区间变为 [left, mid - 1] right = mid - 1; } } // 循环结束后，left 指向的就是满足条件 nums[i] < nums[n-1] 的第一个位置 return nums[left]; } }时间复杂度：O(logN)
空间复杂度：O(1)