力扣Hot100-二分篇

超级好用的二分板子

介绍一个超级好用的二分板子，出自代码源，真的蛮好使的，核心思想就是，以分界线的角度来进行二分。
这里直接给出板子吧，以在有序数组nums（下标为0 - n-1）中找到目标数target为例：

int search(int[] nums, int target) {
    int L = -1, R = nums.length; // 分界线可能位于0的左边，或n-1的右边
    while (L + 1 < R) {
        int M = (L + R) / 2;
        if (nums[M] < target) L = M;
        else R = M;
    }
    if (R < nums.length && nums[R] == target) return R; // 根据题意进行返回
    else return -1;
}

一些细节：

• 分界线不是某个特定的下标，而是位于两个下标之间，二分结束后，L + 1 == R，L 与 R 之间的即为分界线。
• 假设要在下标为0 - n-1的数组中找分界线，则初始L = -1, R = n，因为分界线可能位于0 的左边或者 n-1 的右边。
• 如果最后得到的L == -1，则分界线位于0 的左边，即所有数都不满足某个条件。
• 如果最后得到的L == n-1，则分界线位于n-1 的右边，即所有数都满足某个条件。
• 最后得到L 可能为 -1, R 可能为 n，要对这种边界情况进行处理，防止越界。

除了第 33 题，其他题目使用该板子都能较为轻松的解决，所以只总结第 33 题。

33.搜索旋转排序数组

原题链接
这道题，用这个二分板子就有点不太好使了，为什么呢？
因为这道题的区间一开始是不明确的，而其他题目，我们可以在一开始就对区间进行划分，这么说可能有点抽象，画下图吧：

在完成对区间的划分后，我们就可以根据这个条件来进行二分，最终求得分界线。
而这道题不行，数组旋转后，不满足升序，我们找不到一个条件来帮助我们对区间进行划分，以求得target。
也就是说这个二分板子针对的是区间，求得的是分界线，而非一个数。
板子不好使，但不代表这道题不能使用二分来写，抓住该题的关键点：

• 每一次二分，一个区间是有序的，一个区间是无序的。
• 我们无法判断target是否存在于无序区间中，但可以判断target是否存在于有序区间，若target不在有序区间，则在无序区间。

代码实现

class Solution {
    public int search(int[] nums, int target) {
        int L = 0, R = nums.length - 1;

        while (L <= R) {
            int M = (L + R) / 2;
            if (nums[M] == target) return M;
            // 还需要判断下M右边的那个数
            if (M + 1 <= R && nums[M + 1] == target) return M + 1;
            // 二分后，一定一边有序，一边无序
            // 左边有序
            if (nums[M] > nums[L]) {
                if (target >= nums[L] && target < nums[M]) {
                    // 目标数在左边
                    R = M - 1;
                } else L = M + 1;
            }
            // 右边有序
            else {
                if (target > nums[M] && target <= nums[R]) {
                    // 目标数在右边
                    L = M + 1;
                } else R = M - 1;
            } 
        }

        return -1;
    }
}

---

至于那道困难题为啥不总结，只能说是做不了一点😅