当前位置：首页 > news >正文

Leetcode百题斩-二分搜索

news 2025/7/13 5:58:12

二分搜索也是一个很有趣的专题，被做过的题中，刚好一个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;}}
}

最终，二分也完结撒花了