小鸡玩算法-力扣HOT100-二分查找(下)

一.搜索旋转排序数组

问题概述：

整数数组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)的算法解决此问题。

思路：

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.

如果目标值在黄色区域，就是正常的二分查找，如果不在，就需要重新划分。

if(nums[l]<=nums[mid])对应左侧单调递增的区域，if(target>=nums[l]&&target<nums[mid])，并且target落在这个区域上

代码：

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

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

问题概述：

已知一个长度为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)的算法解决此问题。

思路：

最小值一定是连续部分的第一个位置，如果mid落在左部分，那区间就为[mid+1,r],如果落在右半部分区间就为[l,mid]。为啥不是mid-1呢，因为mid已经在右半部分了，那每个都有可能是最小值了。

怎么确定mid落在哪个部分呢，因为左半部分任何一个值都要大于右半部分的最大值，就通过这个条件去判断即可。

为啥while里面不是l<=r呢，因为标准的二分查找是给你目标去找，那现在是通过索引去锁定最小值，当相等的时候跳出输出就可。

代码：

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

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

问题概述：

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

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

思路：

【【力扣hot100】【LeetCode 4】 寻找两个正序数组的中位数 ｜二分查找】https://www.bilibili.com/video/BV1ss5xzAEwR?vd_source=1d2dfd176f1f132070d67162d5977008

采用数组划分的思想

找到俩个数组的划分点i和j,他们隐藏的默认关系是i+j=（m+n+1）/2,所以只要确定1个，另一个也就确定了。那基于效率考虑，就找数组短的那个划分点。然后进行不断扯绳子（也就是上面俩个式子的判断），去锁定最后的i。

如果俩个数组数量和为奇数，就是绳子当中最大那个数，如果是偶数就是绳子当中最大那个数+除绳子外的最小那个数，然后除以2.

当中有特殊情况，比如一根绳子都在一个数组上，设置Integer.MIN_VALUE和Integer.MAX_VALUE，其实都是为了满足上面那俩个式子。

r得从m开始，不是m-1，因为绳子要够到所有值，那限制就是i，i的最大限制就是r，l=0可以取到第一个没影响，r=m-1最后一个就取不到了。

代码：

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; int l=0; int r=m; int median1=0; int median2=0; while(l<=r){ int i=(l+r)/2; int j=(m+n+1)/2-i; int numilef=(i==0) ? Integer.MIN_VALUE : nums1[i-1]; int numirig=(i==m) ? Integer.MAX_VALUE : nums1[i]; int numjlef=(j==0) ? Integer.MIN_VALUE : nums2[j-1]; int numjrig=(j==n) ? Integer.MAX_VALUE : nums2[j]; if(numilef<=numjrig&&numjlef<=numirig){ median1=Math.max(numilef,numjlef); median2=Math.min(numirig,numjrig); break; }else if(numilef>numjrig){ r=i-1; }else{ l=i+1; } } return (n+m)%2==0 ? (median1+median2)/2.0 : median1; } }