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

一.搜索旋转排序数组问题概述整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了向左旋转使数组变为[nums[k], nums[k1], ..., 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(targetnums[l]targetnums[mid])并且target落在这个区域上代码class Solution { public int search(int[] nums, int target) { int l0; int rnums.length-1; while(lr){ int mid(lr)/2; if(nums[mid]target){ return mid; } if(nums[l]nums[mid]){ if(targetnums[l]targetnums[mid]){ rmid-1; }else{ lmid1; } }else{ if(targetnums[mid]targetnums[nums.length-1]){ lmid1; }else{ rmid-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落在左部分那区间就为[mid1,r],如果落在右半部分区间就为[l,mid]。为啥不是mid-1呢因为mid已经在右半部分了那每个都有可能是最小值了。怎么确定mid落在哪个部分呢因为左半部分任何一个值都要大于右半部分的最大值就通过这个条件去判断即可。为啥while里面不是lr呢因为标准的二分查找是给你目标去找那现在是通过索引去锁定最小值当相等的时候跳出输出就可。代码class Solution { public int findMin(int[] nums) { int l0; int rnums.length-1; while(lr){ int mid(lr)/2; if(nums[mid]nums[r]){ lmid1; }else{ rmid; } } return nums[l]; } }三.寻找两个正序数组的中位数问题概述给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log (mn))。思路【【力扣hot100】【LeetCode 4】 寻找两个正序数组的中位数 二分查找】https://www.bilibili.com/video/BV1ss5xzAEwR?vd_source1d2dfd176f1f132070d67162d5977008采用数组划分的思想找到俩个数组的划分点i和j,他们隐藏的默认关系是ijmn1/2,所以只要确定1个另一个也就确定了。那基于效率考虑就找数组短的那个划分点。然后进行不断扯绳子也就是上面俩个式子的判断去锁定最后的i。如果俩个数组数量和为奇数就是绳子当中最大那个数如果是偶数就是绳子当中最大那个数除绳子外的最小那个数然后除以2.当中有特殊情况比如一根绳子都在一个数组上设置Integer.MIN_VALUE和Integer.MAX_VALUE其实都是为了满足上面那俩个式子。r得从m开始不是m-1因为绳子要够到所有值那限制就是ii的最大限制就是rl0可以取到第一个没影响rm-1最后一个就取不到了。代码class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { if(nums1.lengthnums2.length){ return findMedianSortedArrays(nums2,nums1); } int mnums1.length; int nnums2.length; int l0; int rm; int median10; int median20; while(lr){ int i(lr)/2; int j(mn1)/2-i; int numilef(i0) ? Integer.MIN_VALUE : nums1[i-1]; int numirig(im) ? Integer.MAX_VALUE : nums1[i]; int numjlef(j0) ? Integer.MIN_VALUE : nums2[j-1]; int numjrig(jn) ? Integer.MAX_VALUE : nums2[j]; if(numilefnumjrignumjlefnumirig){ median1Math.max(numilef,numjlef); median2Math.min(numirig,numjrig); break; }else if(numilefnumjrig){ ri-1; }else{ li1; } } return (nm)%20 ? (median1median2)/2.0 : median1; } }