Leetcode百題斬-二分搜索

二分搜索也是一個很有趣的專題，被做過的題中，剛好一個Easy，一個Medium和一個Hard，剛好可以看看，二分搜索的三個難度等級都是啥樣的。

124. Binary Tree Maximum Path Sum[Hard]（詳見二叉樹專題）

先來看Hard，一看不對勁，這一題和二分搜索不能說是毫無關系，只能說毫不相關，這就是個純純的二叉樹的題，趕緊從這個專題剔除，寫到二叉樹專題里了

Leetcode百題斬-二叉樹-最大路徑和-CSDN博客

35. Search Insert Position[Easy]

思路：經典二分，求大于等于當前數的第一個位置，果然easy題，那么直接來

/*
Author Owen_Q
*/
public class InsertSearcher {public static int searchInsert(int[] nums, int target) {int en = nums.length - 1;int st = 0;int mid = (st + en) / 2;while (st <= en) {if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {en = mid - 1;} else {st = mid + 1;}mid = (st + en) / 2;}return st;}
}

多想一步：考慮元素可重通用寫法

?既然是easy題，這一題其實也很有代表性了，那么我們就多想一步，考慮一下當元素可重時的通用寫法，就是將等于mid的場景直接去掉。這樣就可以形成通用模板了，說不定后面還能用到

/*
Author Owen_Q
*/
public class InsertSearcher {public static int accurateSearchInsert(int[] nums, int target) {int en = nums.length - 1;int st = 0;while (st <= en) {int mid = (st + en) / 2;if (nums[mid] >= target) {en = mid - 1;} else {st = mid + 1;}}return st;}
}

33. Search in Rotated Sorted Array[Medium]

思路：將數組旋轉，然后求當前元素是否在數組中。經典二分的變種題，分情況討論一下即可

首先特判mid，st和en三個點，如果找到直接返回。

我們的目標就是為了找到target個mid的關系，從而縮小二分的區間

下面，我們主要討論值在左邊的場景，因為值在右邊的場景把值在左邊的場景排除掉即可獲得

首先，我們可以根據target和num[mid]的大小關系來進行分類，然后再根據mid在大小分界的左邊還是右邊進行分類

當target<num[mid]時，
- 我們先假設mid在分界的左側（num[en] < num[st] < num[mid]），那么此時mid的左側有序，此時如果希望target在mid左側，那么target一定得大于num[st]，否則，若target再小一點就會轉到右邊去了，即target > num[st]?
- 我們再假設num[mid]在分界的右側（num[mid] < num[en] < num[st] ），此時左側無序了，右側有序了，那么此時我們不難發現，這種情況肯定沒法在右側。于是只需要找到這種情況即可。即num[st] > num[mid]?
當target>num[mid]時
- 還是一樣，我們先假設mid在分界的左側（num[en] < num[st] < num[mid]），此時mid的左側有序，那么num[mid]就是最大值，而target比最大值還大，顯然不成立
- 由此可知，此時mid一定在分界的右側（num[mid] < num[en] < num[st]），那么mid右側有序，此時，target值一定要大于num[st]，確保其轉到左邊去

/*
Author Owen_Q
*/
public class RotatedSearcher {public static int search(int[] nums, int target) {int en = nums.length - 1;int st = 0;int mid = (st + en) / 2;while (st <= en) {if (nums[mid] == target) {return mid;} else if (nums[st] == target) {return st;} else if (nums[en] == target) {return en;} else if ((nums[mid] > target && ((nums[st] < target) || nums[st] > nums[mid])) || (nums[mid] < target && nums[mid] < nums[st] && nums[st] < target)) {en = mid - 1;} else {st = mid + 1;}mid = (st + en) / 2;}return -1;}
}

153. Find Minimum in Rotated Sorted Array[Medium]

思路：尋找旋轉數組中的最小值

依舊是分情況討論。

首先我們先找一種最簡單的情況，就是數組內部有序，即 $nums[st] \leqslant nums[mid] \leq nums[en]$ ，那么此時可以直接退出二分，因為st就是最小值所在點

接下來，我們看一下兩種常規情況?

第一種就是當前搜索到的值比兩側都大，即 $nums[mid] \geq nums[st] \wedge nums[mid] \geq nums[en]$ ，那么此時最小值一定在右側

第二種則是當搜索到的值比兩側都小，即 $nums[mid] \leq nums[st] \wedge nums[mid] \leq nums[en]$ ，那么此時最小值要么在左側，要么自身就是最小值

/*
Author Owen_Q
*/
public class RotatedMinimum {public static int findMin(int[] nums) {int st = 0;int en = nums.length - 1;int mid = (st + en) / 2;while (st <= en) {if (nums[st] <= nums[mid] && nums[mid] <= nums[en]) {return nums[st];} else if (nums[mid] >= nums[st] && nums[mid] >= nums[en]) {st = mid + 1;} else {en = mid;}mid = (st + en) / 2;}return nums[st];}
}

74. Search a 2D Matrix[Medium]（詳見矩陣專題）

思路：這一題極其熟悉，是不是之前做過，果然，在矩陣專題里有原題，還是線性復雜度的，那既然有更好的做法，就不看這里log復雜度的二分方案了

Leetcode百題斬-矩陣-矩陣搜索-CSDN博客

34. Find First and Last Position of Element in Sorted Array[Medium]

思路：尋找元素在數組中的區間。這剛好上面多想一步的模版就可以用上了。模版的內容是找到大于等于當前數的第一個值，剛好可以作為區間起點，區間終點就是大于等于下一個數的前一個位置。若當前數不在區間中，那么大于等于當前數和大于等于下一個數一定是同一個位置，區間終點建議后會導致右區間大于左區間，直接特判找不到即可

/*
Author Owen_Q
*/
public class RangeSearcher {public static int[] searchRange(int[] nums, int target) {int[] result = new int[2];result[0] = InsertSearcher.accurateSearchInsert(nums, target);result[1] = InsertSearcher.accurateSearchInsert(nums, target + 1) - 1;if (result[0] > result[1]) {result[0] = -1;result[1] = -1;}return result;}
}

4. Median of Two Sorted Arrays[Hard]

思路：給定兩個有序數組，要求在log時間復雜度內尋找中位數。換個思路，尋找中位數，思路上來說就是尋找兩數組合并后的中間兩個數求個平均值。針對長度為? $nums1Len$ ?和? $nums2Len$ ?的數組，中間的位置就在? $\frac{nums1Len + nums2Len}{2}$ ?和? $\frac{nums1Len + nums2Len - 1}{2}$ 。于是，問題轉化為，如何求兩個有序數組的第? $k$ ?個位置的值。如果直接將倆數組合并，那妥妥線性復雜度，如何利用二分的思路將復雜度降下來呢？二分的思路一般就是每次將數據規模降低一半，恰巧，其實為了求第? $k$ ?個位置的數，其? $\frac{k-1}{2}$ ?位置的及前方的數一定位于同一個數組，那么比較倆數組? $\frac{k-1}{2}$ ?位置的數，并將小的直接舍棄，就做到了對半降低數據量。最終如果某個數組空了，或者不需要舍棄了，即可直接返回結果。這題最難的點就是對半邊界的取值，一不小心就會出現偏差，還是細致至上了。

/*
Author Owen_Q
*/
public class ArrayMedian {public static double findMedianSortedArrays(int[] nums1, int[] nums2) {int nums1Len = nums1.length;int nums2Len = nums2.length;int medianMin = (nums1Len + nums2Len - 1) / 2;int medianMax = (nums1Len + nums2Len) / 2;return ((double)getMedian(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, medianMin) + (double)getMedian(nums1,0, nums1Len - 1, nums2, 0, nums2Len - 1, medianMax)) / 2.0;}private static int getMedian(int[] nums1, int nums1Start, int nums1End, int[] nums2, int nums2Start, int nums2End,int pos) {if (nums1Start > nums1End) {return nums2[nums2Start + pos];}if (nums2Start > nums2End) {return nums1[nums1Start + pos];}if (pos == 0) {return Math.min(nums1[nums1Start + pos], nums2[nums2Start + pos]);}int num1pos = Math.min(nums1End, nums1Start + (pos - 1) / 2);int num2pos = Math.min(nums2End, nums2Start + (pos - 1) / 2);if (nums1[num1pos] <= nums2[num2pos]) {int newPos = pos + nums1Start - num1pos - 1;return getMedian(nums1, num1pos + 1, nums1End, nums2, nums2Start, nums2End, newPos);} else {int newPos = pos + nums2Start - num2pos - 1;return getMedian(nums1, nums1Start, nums1End, nums2, num2pos + 1, nums2End, newPos);}}
}

多想一步：拆分區間

其實上述思路是用到了log復雜度將數據量減半的思路，但其實還有一個更通用的二分方式，就是二分特定位置。

針對中位數，我們可以將數組拆分成左右兩個區間，要求兩個區間的元素數量完全相同，或者左側比右側少一個元素。并且要求左側的數一定都小于等于右側的數。此時，若數組大小為奇數，則右側最小值為中位數，否則，左側最大值和右側最小值的平均值即為中位數。

那么問題就簡化為了，如何尋找到劃分區間的位置。首先，我們可以將短的數組作為操作數組，因為只要短的數組的劃分位置定了，那么根據元素數量就一定能算出長的數組的劃分位置。假設數組1的長度為? $nums1Len$ ，數組2的長度為? $nums2Len$ ，數組1的劃分位置為? $mid$ ，那么數組2的劃分位置就是? $(nums1Len + nums2Len) / 2 - mid$ 。于是我們二分短的數組的劃分位置，即可得到長數組的劃分位置，再檢查一下是否左邊最大值小于等于右邊最小值即可。至于二分移動方案，若左上大于右下，則劃分位置需要向左移，否則向右移。最后注意一下當劃分位置移動到邊界時，那么邊界的數如果不存在則不參與比較，可能用個int的最大值和最小值來跳過比較即可。

/*
Author Owen_Q
*/
public class ArrayMedian {public static double findMedianSortedArraysByDivider(int[] nums1, int[] nums2) {int nums1Len = nums1.length;int nums2Len = nums2.length;if (nums1Len > nums2Len) {return findMedianSortedArraysByDivider(nums2, nums1);}int st = 0;int en = nums1Len;int medianMin = 0;int medianMax = nums1Len - 1;while (st <= en) {int mid = (st + en) / 2;int mid2 = (nums1Len + nums2Len) / 2 - mid;int left1 = mid == 0 ? Integer.MIN_VALUE : nums1[mid - 1];int left2 = mid2 == 0 ? Integer.MIN_VALUE : nums2[mid2 - 1];int right1 = mid == nums1Len ? Integer.MAX_VALUE : nums1[mid];int right2 = mid2 == nums2Len ? Integer.MAX_VALUE : nums2[mid2];medianMin = Math.max(left1, left2);medianMax = Math.min(right1, right2);if (medianMin <= medianMax) {break;} else if (left1 > right2) {en = mid - 1;} else {st = mid + 1;}}if ((nums1Len + nums2Len) % 2 == 1) {return medianMax;} else {return (double)(medianMin + medianMax) / 2.0;}}
}

最終，二分也完結撒花了