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]

思路：寻找旋转数组中的最小值

依旧是分情况讨论。

首先我们先找一种最简单的情况，就是数组内部有序，即，那么此时可以直接退出二分，因为st就是最小值所在点

接下来，我们看一下两种常规情况 

第一种就是当前搜索到的值比两侧都大，即，那么此时最小值一定在右侧

第二种则是当搜索到的值比两侧都小，即，那么此时最小值要么在左侧，要么自身就是最小值

/*
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时间复杂度内寻找中位数。换个思路，寻找中位数，思路上来说就是寻找两数组合并后的中间两个数求个平均值。针对长度为  和  的数组，中间的位置就在  和 。于是，问题转化为，如何求两个有序数组的第  个位置的值。如果直接将俩数组合并，那妥妥线性复杂度，如何利用二分的思路将复杂度降下来呢？二分的思路一般就是每次将数据规模降低一半，恰巧，其实为了求第  个位置的数，其  位置的及前方的数一定位于同一个数组，那么比较俩数组  位置的数，并将小的直接舍弃，就做到了对半降低数据量。最终如果某个数组空了，或者不需要舍弃了，即可直接返回结果。这题最难的点就是对半边界的取值，一不小心就会出现偏差，还是细致至上了。

/*
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的长度为 ，数组2的长度为 ，数组1的划分位置为 ，那么数组2的划分位置就是 。于是我们二分短的数组的划分位置，即可得到长数组的划分位置，再检查一下是否左边最大值小于等于右边最小值即可。至于二分移动方案，若左上大于右下，则划分位置需要向左移，否则向右移。最后注意一下当划分位置移动到边界时，那么边界的数如果不存在则不参与比较，可能用个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;
        }
    }
}

最终，二分也完结撒花了