红蓝二分法，边界判定不用愁

Shio2022-08-142023-12-07

:closed_book::blue_book:红蓝二分法解题

:mag:红蓝二分法讲解：

特此声明：本文模板非原创，核心内容均转自B站五点七边，本人主要进行简要介绍，相应题目代码展示，持续更新中……

关于红蓝二分法，五点七边以给出很不错的讲解：

二分查找为什么总是写错？_哔哩哔哩_bilibili

leetcode 大佬讲解红蓝二分法

蓝红二分法单模板秒杀二分查找

:star2:二分的本质：

如果我们能够通过某种方式将一个区间划分成两个区间，左边区间满足某种特性；右边区间不满足某种特性。
那么我们就能够通过二分法来寻找左区间的右边端点或者右区间的左边端点

有单调性一定可以二分，但是二分不一定要有单调性

通常二分法的思路是通过二分不断缩小结果范围直到确认结果或者区间不存在

而红蓝二分法则是逆向思路，通过不断扩大非结果区间的范围直到直到确认结果或者区间不存在

通常二分法的思路对应的各种左闭右闭或者左闭右开往往面临繁琐的边界问题，虽然通过大量练习也能熟能生巧，但红蓝二分提供的简易思路可以摒弃复杂的边界问题，更加贴近二分的本质——循环不变量

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

红蓝二分模板：

l = -1, r = N;						//初始化，保证l和r不在搜索区间内部，保证循环不变量				
while l + 1 != r
    m = l + (r - l) / 2           	//此处预防越界，只是和(l + r) / 2写法不同
    if isBlue(m)				  	// isBlue()是抽象出来的用来判断特性的方法
        l = m
    else
        r = m
return l or r						//因题而异

:grey_question:二分题目总结

完全有序

梦开始的地方，基础的二分查找

:star: 704.二分查找

力扣题目链接(opens new window)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

1
2
3

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

1
2
3

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

红蓝二分法解法：

 class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length;
        while(l + 1 != r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) return m;
            else if (nums[m] > target) r = m;
            else l = m;
        }
        return -1;
    }
}

35.搜索插入位置

二分查找的变式，感受查找边界

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = -1, r = nums.length;
        while (l + 1 != r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) r = m;
            else l = m;
        }
        return r;
    }
}

:star:34. 在排序数组中查找元素的第一个和最后一个位置

二分查找边界的复合，进一步感受边界

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int result[] = {getLeft(nums,target),getRight(nums,target)};
        return result;
    }
    private int getLeft(int[] nums, int target) {
        int l = -1, r = nums.length;
        while (l + 1 != r) {
            int m = l + ((r - l) >> 1);
            if (nums[m] >= target) r = m;
            else l = m;
        }
        if (r == nums.length || nums[r] != target  ) return -1;
        return r;
    }
    private int getRight(int[] nums, int target) {
        int l = -1, r = nums.length;
        while (l + 1 != r) {
            int m = l + ((r - l) >> 1);
            if (nums[m] <= target) l = m;
            else r = m;
        }
        if (l == -1 || nums[l] != target) return -1;
        return l;
    }
 
}

不完全有序

(旋转排序数组系列)

局部有序，注意循环不变量

:star:153. 寻找旋转排序数组中的最小值

已知一个长度为 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) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解法一

class Solution {
    public int findMin(int[] nums) {
        int l = -1, r = nums.length;
        int m = l + ((r - l) >> 1);
        if(nums[m] <= nums[r - 1]) {
            r = m;
            while (l + 1 != r) {
                m = l + ((r - l) >> 1);
                if (nums[m] <= nums[r]) r = m;
                else l = m;
            }
        }else {
            l = m;
            while (l + 1 != r) {
                m = l + ((r - l) >> 1);
                if (nums[m] >= nums[l]) l = m;
                else r = m;
            }
        }
        return nums[r];
    }
}

解法二、

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int l=-1, r=n;
        while (l+1 != r) {
            int mid = l+(r-l)/2;
            int target = r == n ? nums[n-1] : nums[r];
            if (nums[mid] > target) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return nums[r];
    }
}

:star:154. 寻找旋转排序数组中的最小值 II

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须尽可能减少整个过程的操作步骤。

示例 1：

输入：nums = [1,3,5]
输出：1

示例 2：

输入：nums = [2,2,2,0,1]
输出：0

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶：这道题与寻找旋转排序数组中的最小值类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int r = n-1;
        while (nums[r] == nums[0] && r > 0) {
            r--;
        }
        int last = nums[r];
        int l = -1;
        ++r;
        n = r;
        while (l+1 != r) {
            int mid = l+(r-l)/2;
            int target = r == n ? last : nums[r];
            if (nums[mid] > target) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return nums[r];
    }
}

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., 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) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

:star:81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

进阶：

这是搜索旋转排序数组的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么

class Solution {
    int n;
    public boolean search(int[] nums, int target) {
        int t = findMin(nums);
        System.out.println(t);
        int l = -1, r = n;
        if (nums[t] <= target && target <= nums[n - 1]) {
            l = t - 1;
        } else {
            r = t;
        }
        while (l + 1 != r) {
            int m = (r + l) >> 1;
            if (nums[m] == target) return true;
            else if (nums[m] > target) r = m;
            else l = m;
        }
        return false;
    }
     public int findMin(int[] nums) {
        n = nums.length;
        int r = n-1;
        while (nums[r] == nums[0] && r > 0) {
            r--;
        }
        int last = nums[r];
        int l = -1;
        ++r;
        n = r;
        while (l+1 != r) {
            int mid = l+(r-l)/2;
            int target = r == n ? last : nums[r];
            if (nums[mid] > target) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return r;
    }
}

:star:162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

class Solution {
    public int findPeakElement(int[] nums) {
        int l = -1, r = nums.length;
        int m = 0;
        while (l + 1 != r) {
           m = l + ((r - l) >> 1);
           if (m >= nums.length - 1) r = m;  
           else if ( nums[m] > nums[m+1]) r = m;
           else l = m;
        }
        return r;
    }
}

二维数组

:star:74. 搜索二维矩阵

难度中等

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int l = -1, r = matrix.length * matrix[0].length;
        while (l + 1 != r) {
            int m = l + ((r - l) >> 1);
            int value = get(matrix,m);
            if (value == target) return true;
            else if (value > target) r = m;
            else l = m;
        }
        return false;
    }
    private int get(int[][] matrix, int index) {
        int m = matrix.length, n = matrix[0].length;
        int i = index / n, j = index % n;
        return matrix[i][j]; 
    }
}

其他

367. 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。
示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

1 <= num <= 231 - 1

//直接暴力用大数了
import java.math.*;
class Solution {
    public boolean isPerfectSquare(int num) {
        BigInteger l =BigInteger.valueOf(-1);
        BigInteger r =BigInteger.valueOf((num >> 1) + 2);
        BigInteger x = BigInteger.valueOf(num);
        BigInteger m;
        while (!l.add(BigInteger.ONE).equals(r)) {
            m = l.add(r).divide(BigInteger.TWO);
            if (m.multiply(m).equals(x)) return true;
            else if (m.multiply(m).compareTo(x) == -1) l = m;
            else r = m;
        }
        return false;
    }
}

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 231 - 1

//暴力大数
import java.math.*;
class Solution {
    public int mySqrt(int x) {
        BigInteger l = BigInteger.valueOf(-1);
        BigInteger r = BigInteger.valueOf((x >> 1) + 2);
        BigInteger num = BigInteger.valueOf(x); 
        while (!l.add(BigInteger.ONE).equals(r)) {
            BigInteger m = l.add(r).divide(BigInteger.TWO);
            if (m.multiply(m).compareTo(num) == 1) r = m;
            else l = m;
        }
        return l.intValue(); 
    }
}

class Solution {
    public int mySqrt(int x) {
        if (x == 2 || x == 3 || x == 1) return 1;
        if (x == 0) return 0;
        //上面两行均是为了防止 m == 0的情况，而后面为什么要用x/m<m 而不是 m*m>x则是为了防止越界错误
        int l = -1 , r = (x >> 1) + 2;
        while (l + 1 != r) {
            int m = l + ((r - l)>>1);
            if (x / m < m) r = m;
            else l = m;
        }
        return l; 
    }
}