详解二分查找法

文章目录

详解二分查找法
- 概念
- 应用场景（适用条件）
- 解题步骤
- - 代码框架
  - - 关于这段代码的keys
    - - 为什么 while 循环的条件中是
      - 什么时候应该停止搜索呢？
      - 为什么 left = mid + 1，right = mid - 1？
    - 算法缺陷
    - 寻找左侧边界的二分搜索
    - 寻找右侧边界的二分搜索
    - bisect_left
    - bisect_right
  - summary
- 引申-二分思想
- - 例题参考
  - - leetcode-29-两数相除
    - leetcode-50-Pow(x, n)
- 例题参考
- - 解决topK问题
  - leetcode-35-搜索插入位置
  - leetcode-154-寻找旋转数组的最小值
  - leetcode-153-寻找旋转数组的最小值
  - leetcode-33-在旋转数组中寻找值
  - leetcode-209-最小尺寸的子数组
  - leetcode-222-完全二叉树的节点个数
  - leetcode-300-最长的递增子列表长度
  - - 变形
  - Leetcode-315-计算右边小于当前元素的个数
  - leetcode-400-第 n 位
  - leetcode-436-寻找右间隔
  - leetcode-352-不相邻间隔
  - leetcode-475-暖气
  - leetcode-497-随机点
  - leetcode-354-Russian doll
  - leetcode-528-random pick with weight

2019/12/26 add 更新总结

2019/12/26 add 二分思想

2022/10/04 add 例题 153

2022/10/05 add 例题 33

references：

详解二分查找算法

Java常见算法之二分法查找算法详解

java实现二分查找-两种方式

概念

二分查找法，是在已经排好序的序列中，定义一个起始位置 start(即序列第一个元素)和一个终止位置 end(即序列最后一个元素),通过 mid=(start+end)/2计算出中间位置，通过待查找元素与 mid 中间位置的元素进行比较，如果待查找元素比中间位置 mid 对应的值小，那么将end = mid -1(即将 end 结束位置移动到 mid中间左边一个位置)，如果比中间对应的值大，那么将 start = mid + 1 (即将 start 的位置移动到 mid 右边一个位置)，一直循环查找，直到 start > end,证明没找到对应的元素，停止循环。

注：二分查找法其实一种双指针法

应用场景（适用条件）

至少满足以下两个条件：

已经排好序的序列
需要查找某个或者某多个值

其他：二分查找法常常用以对暴力嵌套循环的优化

解题步骤

代码框架

确定 start，end
处理好问题边界情况

const binarySearch=(nums, target)=>{
    let left = 0; 
    let right = nums.length - 1; // 注意

    while(left <= right) { // 注意
        let mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            // mid is too small
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            // mid is too big
            right = mid - 1; // 注意
        }
    return -1;
}

关于这段代码的keys

为什么 while 循环的条件中是 <=，而不是 < ？

答：因为初始化 right 的赋值是 - 1，即最后一个元素的索引，而不是。

这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为是越界的。

我们这个算法中使用的是 [left, right] 两端都闭的区间。这个区间就是每次进行搜索的区间，我们不妨称为「搜索区间」(search space)。

我个人而言，更喜欢统一成这种闭区间的形式来做题，避免漏掉讨论的情况。
如果想看另一种方法怎么去处理边界，可以参考references中的文章1

什么时候应该停止搜索呢？

当然，找到了目标值的时候可以终止：

    if(nums[mid] ===target){
        return mid;    
    }

但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。

为什么 left = mid + 1，right = mid - 1？

我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。

刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，如何确定下一步的搜索区间呢？

当然是去搜索 [left, mid - 1] 或者 [mid + 1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

算法缺陷

有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

因此由该算法的缺陷衍生出下面两种不同的二分查找算法：

寻找左侧边界的二分搜索

和 bisect_left 一样的思路

const left_bound=(nums, target)=>{
    if (nums.length === 0) return -1;
    let left = 0;
    let right = nums.length-1; // 注意

    while (left <= right) { // 注意
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            // 找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid-1] 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
            right = mid-1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid-1; // 注意
        }
    }
    return left;
};

// 算法会返回 1。这个 1 的含义可以这样解读：nums 中小于 2 的元素有 1 个。
console.info(left_bound([1,2,2,2,3,4],2));
// 算法会返回 4。这个 4 的含义可以这样解读：nums 中小于 3 的元素有 4 个。
console.info(left_bound([1,2,2,2,3,3,3,3,4],3));

寻找右侧边界的二分搜索

区别于 bisect_right，它是返回 right，有少量的应用场景。

const right_bound=(nums, target)=>{
    if(nums.length<=0) return -1;
    let left=0,right=nums.length-1;
    while(left<=right){
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            // 找到 target 时不要立即返回，而是增大「搜索区间」的上界left，在区间 [mid+1,right] 中继续搜索，即不断向右收缩，达到锁定右侧边界的目的。
            left = mid+1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid-1; // 注意
        }
    }
    // 其实return left-1还是right没有区别
    return right;
};
// 算法会返回 3。这个 3 的含义就是右侧边界索引是3。
console.info(right_bound([1,2,2,2,3,4],2));
// 算法会返回 7。这个 7 的含义就是右侧边界索引是7。
console.info(right_bound([1,2,2,2,3,3,3,3,4],3));

bisect_left

如果要向有序数组中插入元素 a, 那么能插入的最左侧的位置是？

const bisect_left=(nums, target)=>{
    if (nums.length === 0) return -1;
    let left = 0;
    let right = nums.length-1; // 注意

    while (left <= right) { // 注意
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] >= target) {
            // 找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid-1] 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
            right = mid-1;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

// 算法会返回 1。
console.info(bisect_left([1,2,2,2,3,4],2));
// 算法会返回 4。
console.info(bisect_left([1,2,2,2,3,3,3,3,4],3));

bisect_right

如果要向有序数组中插入元素 a, 那么能插入的最左侧的位置是？

const bisect_right=(nums, target)=>{
    if(nums.length<=0) return -1;
    let left=0,right=nums.length-1;
    while(left<=right){
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] <= target) {
            // 找到 target 时不要立即返回，而是增大「搜索区间」的上界left，在区间 [mid+1,right] 中继续搜索，即不断向右收缩，达到锁定右侧边界的目的。
            left = mid+1;
        } else {
            right = mid-1; // 注意
        }
    }
    return left;
};
// 算法会返回 4。
console.info(bisect_right([1,2,2,2,3,4],2));
// 算法会返回 8。
console.info(bisect_right([1,2,2,2,3,3,3,3,4],3));

summary

分析二分查找代码时，不要出现 else，全部展开成 else if 方便理解。
注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查。
如需要搜索左右边界，只要在 nums[mid] == target 时做修改即可。搜索右侧时需要减一。
算法的复杂度

时间复杂度：采用的是分治策略，最坏的情况下：O(logN)，最好情况下为O(1)
空间复杂度：算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数。由于辅助空间是常数级别的所以：空间复杂度是O(1);

通过对leetcode例题34以及35的总结，可以总结如下：在用binarySearch搜索target时
- 如果 target 存在：left=right=target 所在索引
- 如果 target 不存在：left=right+1 是数列中如果插入 target，那它应该在的位置

引申-二分思想

二分思想其实是一种很快的解决问题的思想，它可以很契合的应用在一些数学问题的解答上

例题参考

leetcode-29-两数相除

代码参考我的GitHub：leetcode-29

leetcode-50-Pow(x, n)

代码参考我的GitHub：leetcode-50

例题参考

可以参考我的另一篇leetcode刷题记录中的内容：leetcode

解决topK问题

可以参考我的另一篇文章TopK问题三种方法总结

leetcode-35-搜索插入位置

虽然这道题是简单题，但却是利用二分查找法的一个小基础和变形，题意如下：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

// 第一段代码，频繁的处理边界，繁琐
const searchInsert = (nums, target)=>{
    let left=0,right=nums.length;
    while(left<=right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        }else if(mid===nums.length-1&&nums[mid]<target){
            return nums.length;
        } else if (nums[mid] < target && mid + 1 < nums.length && nums[mid + 1] > target) {
            return mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    return 0;
};
// 第二段代码，是不是和查找左右边界有异曲同工之处呢？边界条件处理少，不容易漏情况！
const searchInsert1=(nums,target)=>{
    let left=0,right=nums.length-1;
    if(nums[right]<target) return right+1;
    while(left<=right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        }else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    // (left,right);
    return left; //至此，我们知道了，可以利用left的取值找到待插入的位置
};

leetcode-154-寻找旋转数组的最小值

虽然题目给说的花里胡哨的，但其实旋转后的数组我们还是可以看成只旋转了一次，数组被分成了两段有序数据，我们只需求得分隔的地方在哪里即可，
我们称之为分隔点，因为数组其实分隔点两边都是有序的，所以我们可以用二分查找法来找寻分隔点
对于 mid 有两种情况：
1. 位于数组中间，它的左右均有值，针对这种情况又有几种分类
    a. 分隔点就在 mid 或 mid + 1 eg: 
        i. [4,5,3] mid-1<mid>mid+1 所以 mid+1 所在位置就是所求分隔点即最小值所在点，但针对有重复值的情况，我们简化成 mid>mid+1
        ii. [3,1,2] mid-1>mid<mid+1 此时 mid 所在位置即为分隔点，但针对有重复值的情况，我们简化成 mid-1>mid
    b. 分隔点不在 mid 或 mid + 1，此时 mid-1<=mid<=mid+1 这个情况涉及的场景更多，更复杂，此时还要跟左右对比
        i. 先不考虑重复的场景 [4,5,6,7,1] mid>right 对于递增的序列而言出现这种场景则 left = mid + 1
        ii. [5,1,2,3,4] left>mid 对于递增的序列出现这种场景则 right=mid-1
        iii. 如果出现了重复的倘若满足 i ii 也能继续解决问题，如果 left==mid==right [3, 3, 1, 3] 则需要递归一下
        iv. 最后 [1,2,3,4] 这种场景直接返回 0 位置的值即可
2. 位于边界，它的左侧没值或者右侧没值
    a. 左侧没值：[2,1] 如果 mid>mid+1 则为 mid+1 否则为 mid
    b. 右侧没值：因为我们 mid 使用的是 (left+right)//2 向下取整所以最终不会出现这种场景
时间复杂度：O(N) 通常情况下为 O(logN) 当全是重复值的时候则为 O(N)
空间复杂度：O(1) 没有产生额外的空间占用

class Solution:
    def findMin0(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        if left == right:
            return nums[0]
        while left <= right:
            mid = (left + right) // 2
            if mid - 1 >= 0 and mid + 1 < len(nums):
                # 极为特殊的情况下：我们在 mid 附近找到了变异的点
                if nums[mid - 1] > nums[mid]:
                    return nums[mid]
                elif nums[mid + 1] < nums[mid]:
                    return nums[mid + 1]
                elif nums[mid - 1] <= nums[mid] <= nums[mid + 1]:
                    # 如 [4,5,6,7,3]
                    if nums[right] < nums[mid]:
                        left = mid + 1
                    # 如 [7,1,2,3,4]
                    elif nums[left] > nums[mid]:
                        right = mid - 1
                    elif nums[right] == nums[mid] == nums[left]:
                        left_min = right_min = nums[mid]
                        if mid > left:
                            left_min = self.findMin(nums[left:mid])
                        if mid < right:
                            right_min = self.findMin(nums[mid:right])
                        return min(left_min, right_min)
                    else:
                        return nums[0]
            # mid 位于边界处 [2,0,1]
            elif mid - 1 < 0:
                return nums[mid + 1] if nums[mid] > nums[mid + 1] else nums[mid]

    def findMin(self, nums: List[int]) -> int:
            """
            题解方法，通过和右侧不停对比
            :param self:
            :param nums:
            :return:
            """
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right) // 2
                if nums[mid] > nums[right]:
                    left = mid + 1
                elif nums[mid] < nums[right]:
                    right = mid
                else:
                    right -= 1
            return nums[left]

leetcode-153-寻找旋转数组的最小值

153 实际上是 154 题的简化版

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        if left == right:
            return nums[0]
        while left <= right:
            mid = (left + right) // 2
            if mid - 1 >= 0 and mid + 1 < len(nums):
                # 极为特殊的情况下：我们在 mid 附近找到了变异的点
                if nums[mid - 1] > nums[mid]:
                    return nums[mid]
                elif nums[mid + 1] < nums[mid]:
                    return nums[mid + 1]
                elif nums[mid - 1] <= nums[mid] <= nums[mid + 1]:
                    # 如 [4,5,6,7,3]
                    if nums[right] < nums[mid]:
                        left = mid + 1
                    # 如 [7,1,2,3,4]
                    elif nums[left] > nums[mid]:
                        right = mid - 1
                    else:
                        return nums[0]
            # mid 位于边界处 [2,0,1]
            elif mid - 1 < 0:
                return nums[mid + 1] if nums[mid] > nums[mid + 1] else nums[mid]

leetcode-33-在旋转数组中寻找值

解法一：先找到旋转的分界点，参考 153 题的做法，然后对比起始点找到 target 在哪一段，对该段进行二分查找
解法二：我们知道旋转数组无论是从哪里分隔开都会变成一个有序数组+一个无序数组，只需要判断 target 在不在有序数组区间内

class Solution:
    def search0(self, nums: List[int], target: int) -> int:
        """
        题目要求复杂度为 O(logN) 同时考虑到数组为一个基本有序数组所以我们可以使用二分搜索法进行尝试：
        先通过二分查找找到旋转点，然后对两侧分别进行二分查找
        :param nums:
        :param target:
        :return:
        """
        if len(nums) == 1:
            return 0 if target == nums[0] else -1

        def binary_search(nums: list[int], target: int, left: int, right: int) -> int:
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1

        # 寻找旋转点: [left,idx] [idx+1,]
        def find(nums: List[int]) -> int:
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if mid - 1 >= 0 and mid + 1 < len(nums):
                    if nums[mid - 1] < nums[mid] < nums[mid + 1]:
                        if nums[right] <= nums[mid]:
                            left = mid + 1
                        elif nums[left] >= nums[mid]:
                            right = mid - 1
                        else:
                            return -1
                    elif nums[mid - 1] < nums[mid] > nums[mid + 1]:
                        return mid
                    elif nums[mid - 1] > nums[mid] < nums[mid + 1]:
                        return mid - 1
                elif mid - 1 < 0:
                    # 左边界
                    if nums[mid] > nums[mid + 1]:
                        return mid
                    else:
                        left = mid + 1
                elif mid + 1 >= len(nums):
                    # 右边界
                    if nums[mid - 1] > nums[mid]:
                        return mid - 1
                    else:
                        right = mid - 1
            return -1

        rotation_idx = find(nums)
        if rotation_idx == -1:
            return binary_search(nums, target, 0, len(nums) - 1)
        if nums[0] <= target <= nums[rotation_idx]:
            return binary_search(nums, target, 0, rotation_idx)
        elif nums[rotation_idx + 1] <= target <= nums[-1]:
            return binary_search(nums, target, rotation_idx + 1, len(nums) - 1)
        else:
            return -1

    def search(self, nums: List[int], target: int) -> int:
        """
        参考题解的做法：我们知道旋转后的数组，不管是哪里作为分界点都能分成一个有序数组加一个乱序数组
        只需要我们再对首尾元素进行一下判断就可以。
        时间复杂度：O(logN)
        空间复杂度：O(1)
        :param nums:
        :param target:
        :return:
        """
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if target == nums[mid]:
                return mid
            if nums[left] < nums[mid]:
                # 左边有序
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            elif nums[right] > nums[mid]:
                # 右边有序
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            # mid 就是边界
            else:
                left = mid + 1
        return -1

leetcode-209-最小尺寸的子数组

这个题看起来和二分查找没有任何关系，但是使用暴力法却无法解决问题，因为一定会超时，所以我们要创造条件来使用二分查找。

暴力解法时间复杂度为 O(N^2)，我们可以想办法降低，比如降低为 O(NlogN)，但没有条件让我们进行二分查找：

所以我们创造一个递增数组和 target 来使用二分查找法，显然题目显示每个值均为正数，所以他们的和是递增的，递增数组找到了
我们从暴力解法中也能看出来我们要找每个数组值开始的和大于等于 target 的连续长度，所以我们可以将每个数组值前面累加的值一起算进来，这样就总可以在递增数组中找值了。而二分查找找目标值或目标值应该在的位置我们已经很熟悉了。

时间复杂度：O(NlogN)

空间复杂度：O(N)

其他方法：滑动窗口法，本题是一个典型的使用滑动窗口法解决的问题：参考双指针

class Solution:
    def minSubArrayLen0(self, target: int, nums: List[int]) -> int:
        """
        首先想到的就是暴力法来遍历数组
        :param target:
        :param nums:
        :return:
        """
        res, length = sys.maxsize, len(nums)
        for i in range(length):
            tmp = nums[i]
            if tmp >= target:
                res = min(res, 1)
                return res
            for j in range(i + 1, length):
                tmp += nums[j]
                if tmp >= target:
                    res = min(res, j - i + 1)
                    break
        return res if res < sys.maxsize else 0

    # [2, 3, 1, 2, 4, 3]
    # [2, 5, 6, 8, 12, 15]
    def find(self, nums: List[int], left: int, right: int, target: int) -> int:
        while left <= right:
            mid = (left + right) // 2
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        return left

    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        length = len(nums)
        res, tmp, min_len = [0], 0, sys.maxsize
        for i in range(length):
            tmp += nums[i]
            res.append(tmp)
        if res[-1] < target:
            return 0
        for i in range(length):
            tmp_target = target + res[i]
            if res[-1] >= tmp_target:
                idx = self.find(res, i, length, tmp_target)
                min_len = min(min_len, idx - i)
        return min_len if min_len < sys.maxsize else 0

leetcode-222-完全二叉树的节点个数

题目要求复杂度降低到低于 O(N) 所以可以使用二分查找法来解决问题

根据完全二叉树的特点，我们知道如果高度为 h 的完全二叉树（若 h 为 1 则只有根节点），它的节点数在[2^(h-1), 2^h-1] 的区间范围内，此时我们只需要利用二分查找法找到那个节点总数即可
如果判断某个值在不在树中，比如 8 它用二进制表示为 1000，通常最后一层的节点值最高位都是 1，而 0 标识向左，所以从根节点一路向左就来到了节点 8，所以可以通过位运算来判断某个值是否在树中
1. 位运算：检查 1000 可以通过 (1000&100)，检查 1001 可以通过(1001&100, 1001&10, 1001&1)来进行位运算
复杂度分析
1. 时间复杂度：O(logN)^2
2. 空间复杂度：O(1)

class Solution:
    # 时间复杂度：O(N)
    # 空间复杂度：O(N)
    def countNodes0(self, root: Optional[TreeNode]) -> int:
        queue, res = [], 0
        if root is None:
            return res
        queue.append(root)
        while len(queue) > 0:
            first = queue.pop(0)
            res += 1
            first.left and queue.append(first.left)
            first.right and queue.append(first.right)
        return res

    # 根据题解所示用二分查找法结合位运算的方式得到二叉树的节点数
    # 时间复杂度：O(logN)^2
    # 空间复杂度：O(1)
    def countNodes(self, root: Optional[TreeNode]) -> int:
        # 寻找完全二叉树的节点数目，且复杂度低于 O(N)
        # 已知完全二叉树只有最底层是没填满的，所以我们可以一直通过左树得到二叉树的高度
        # 假设只有根节点时为 1 层
        # 从而知道节点数在 [2^(h-1),2^h-1] 之间，我们知道了区间则可以使用二分查找法，判断 mid 是否在树中
        # 具体判断方法：利用位运算判断，比如 8 用二进制表示为 1 0 0 0，其中最高位永远为 1，0 标识向左，则从根节点一路向左能到达 8 所在的节点
        def exists(root: Optional[TreeNode], val: int, h: int) -> bool:
            if h == 1:
                return root.val == val
            bit = 1 << (h-2)
            node = root
            while node is not None and bit > 0:
                if not (bit & val):
                    node = node.left
                else:
                    node = node.right
                bit >>= 1
            return node is not None
        node, level = root, 0
        if node is None:
            return 0
        while node is not None:
            level += 1
            node = node.left
        left = int(math.pow(2, level-1))
        right = int(math.pow(2, level)-1)
        while left <= right:
            mid = int((left + right)//2)
            if exists(root, mid, level):
                left = mid + 1
            else:
                right = mid - 1
        return right

leetcode-300-最长的递增子列表长度

题目可以使用动态规划，也有一个比较高技巧的方式是使用二分查找。题目要求的是子列表的长度，可以升级一下求子列表是什么，具体题解参考下文。

使用动态规划：因为排在前面的连续数目一定比排在后面的多，且与后面的相关，即问题的最优解是由子问题的最优解组成的，因此具有最优子结构性质。于是有了状态转移方程

F(i) = 1 + max(F(i+1),F(i+2)) 其中 nums[i+1]…nums[i+2] > nums[i]

边界条件：F(length-1) = 1

时间复杂度：O(N^2)
空间复杂度：O(N)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        length = len(nums)
        tmp, res = [0] * length, 0
        for i in range(length - 1, -1, -1):
            if i == length - 1:
                tmp[i] = 1
                res = 1
            tmp_0 = 0
            for j in range(i + 1, length):
                if nums[j] > nums[i]:
                    tmp_0 = max(tmp_0, tmp[j])
            tmp[i] = 1 + tmp_0
            res = max(res, tmp[i])
        return res
    def lengthOfLIS_plus(self, nums: List[int]) -> List[int]:
        """
        加强版改编题，求最长的递增子序列
        时间复杂度：O(N^2)
        空间复杂度：O(N^2) 主要是结果数组占用的空间
        :param nums:
        :return:
        """
        length = len(nums)
        res_list = [[] for _ in range(length)]
        res_list[length - 1] = [nums[-1]]
        res = res_list[length - 1]
        for i in range(length - 2, -1, -1):
            tmp_length, tmp = 0, []
            res_list[i] = [nums[i]]
            for j in range(i + 1, length):
                if nums[j] > nums[i] and len(res_list[j]) > tmp_length:
                    tmp_length = len(res_list[j])
                    tmp = res_list[j]
            res_list[i].extend(tmp)
            if len(res) < len(res_list[i]):
                res = res_list[i]
        return res

使用二分查找法：贪心：已知我们想让递增子数组尽可能的长，那么增长速度就得尽可能的慢。

维护一个数组 d[i] 为最长上升子序列，起始时 d[0] 为 nums[0]

为什么最终得到的 d 一定是最长的单增序列，因为首先我们总是添加比最后一个元素大的值所以是单增的

其次，当这个元素比 d[-1] 小的时候，我们用二分查找寻找它应该在的位置，并对该位置的值进行替换，如

果它在中间其实不影响 d 的长度；如果它正好在末尾，那么相当于换了个步长更小的元素，这样也有助于

让 d 继续增长。
时间复杂度：O(NlogN)
空间复杂度：O(N)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        d = []
        for n in nums:
            if not d or n > d[-1]:
                d.append(n)
            else:
                left, right = 0, len(d) - 1
                while left <= right:
                    mid = (left + right) // 2
                    if d[mid] == n:
                        left = mid
                        break
                    elif d[mid] > n:
                        right = mid - 1
                    else:
                        left = mid + 1
                d[left] = n
        return len(d)
    def lengthOfLIS_plus(self, nums: List[int]) -> List[int]:
        """
        加强版改编题：求最长的递增子序列
        时间复杂度：O(NlogN)
        空间复杂度：O(N)
        :param nums:
        :return:
        """
        my_list = []
        for val in nums:
            if not my_list or val > my_list[-1]:
                my_list.append(val)
            else:
                left, right = 0, len(my_list) - 1
                while left <= right:
                    mid = (left + right) // 2
                    # 对于恰好想等的这种情况
                    if my_list[mid] == val:
                        break
                    elif val > my_list[mid]:
                        left = mid + 1
                    else:
                        right = mid - 1
                if left == len(my_list) - 1:
                    my_list[left] = val
        return my_list

变形

334. Increasing Triplet Subsequence

1909. Remove One Element to Make the Array Strictly Increasing

673. Number of Longest Increasing Subsequence

Leetcode-315-计算右边小于当前元素的个数

已知暴力解法时间复杂度为 O(N^2)，我们要找一种优化方式，显然外层循环没办法再优化了，只能是优化内层：
内层可以简化为在一个数组中寻找比某个值小的值的个数，当然是希望数组有序使用二分查找即可，所以首先要让数组有序，同样使用二分查找找到 val
该在的位置并将其插入，时间复杂度为 O(logN)，构建好有序数组后查找比某个元素小的值同样使用二分查找即可，时间复杂度为 O(logN)
因此总体时间复杂度为：O(NlogN)
空间复杂度：O(N) 使用了一个数组来存储有序的值

class Solution:
    def insert(self, nums: List[int], val: int):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == val:
                left = mid
                break
            elif nums[mid] < val:
                left = mid + 1
            else:
                right = mid - 1
        nums.insert(left, val)

    def countSmaller(self, nums: List[int]) -> List[int]:
        """
        已知暴力解法时间复杂度为 O(N^2)，我们要找一种优化方式，显然外层循环没办法再优化了，只能是优化内层：
        内层可以简化为在一个数组中寻找比某个值小的值的个数，当然是希望数组有序使用二分查找即可，所以首先要让数组有序，同样使用二分查找找到 val
        该在的位置并将其插入，时间复杂度为 O(logN)，构建好有序数组后查找比某个元素小的值同样使用二分查找即可，时间复杂度为 O(logN)
        因此总体时间复杂度为：O(NlogN)
        空间复杂度：O(N) 使用了一个数组来存储有序的值
        :param nums:
        :return:
        """
        length = len(nums)
        res = [0] * length
        tmp = []
        for i in range(len(nums) - 1, -1, -1):
            if i == len(nums) - 1:
                res[i] = 0
            else:
                left, right = 0, len(tmp) - 1
                while left <= right:
                    mid = (left + right) // 2
                    if tmp[mid] == nums[i]:
                        right = mid - 1
                    elif nums[i] > tmp[mid]:
                        left = mid + 1
                    else:
                        right = mid - 1
                res[i] = left
            self.insert(tmp, nums[i])
        return res

leetcode-400-第 n 位

可以参考 github repo

leetcode-436-寻找右间隔

可以参考 github repo

leetcode-352-不相邻间隔

这个题非常有意思，如果用普通的数据结构比如列表（数组），时间复杂度总是 O(N)，因为对其操作插入和删除的时间复杂度就是 O(N) ，因此这里引出 python 中的有序字典

reference:

有序结构：SortedContainers

github repo

leetcode-475-暖气

这个题需要擅长去将题目转义

github repo

leetcode-497-随机点

随机等概率找数或者随机等概率找点的题需要注意一点：要等概率查找就意味着找到所有可能的结果然后使 random 函数一次，而后使用相关的算法去寻找真正要求的结果。

github repo

leetcode-354-Russian doll

这个题用二分查找不容易想到，只能说是一种比较怪异的方法上用二分查找提高了效率，这里主要是提一下，重点需要掌握的是其 dp 做法。

github repo

leetcode-528-random pick with weight

github repo

详解二分查找法