CS study

Appearance

Binary Search Summary ​

基本原理：在有序数组定位目标值target，根据中点和target的大小关系定位。 双闭区间模版

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

问题: 如何判断while loop是 l<ror l<=r or l+1<=r?

取决于决定采用那种区间。分别为l~r表示的是左闭右开区间[l,r)还是左闭右闭[l,r]还是双开区间(l,r)

1.基础二分法：在有序数组上二分index寻找某个nums[i]==target ​

1.1 基础：查找边界： ​

定义：在一个有序数组中，找到目标值的第一个或最后一个位置。数组有重复元素，需要定位边界。

红蓝分区法：把array分成2个区间，左边是红区，右边是蓝区。红蓝区分别满足和target相关的不同条件。target划分给红区还是蓝区？

问题:如何知道target在哪个区间？

寻找target的左边界:

收缩右边届 if nums[mid]==target: right = mid-1

寻找target右边届:

收缩左边界 if nums[mid]==target: left = mid+1

循环不变量：当收缩右边界时 nums[left-1] < target, nums[right+1] >= target始终成立

左边界模版:

python
def find_left_bound(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    return left if left < len(nums) and nums[left] == target else -1

1.2 进阶 ​

常用思路： 先排序+二分，binary search包装成helper function，在main function中调用helper function，在有序数组上binary search，根据题目要求得出target

2. 二分答案 ​

二分答案中left, right, mid不再表示array中的index，而是具体数值。

把 nums[m] < > target 变成 check(m,target,x...),一个关于m和target的单调函数 helper function， return True or False。

如何写check()？ 1. 明确单调性，方程的x y值， 判断是求最小valid / 最大valid 2.明确check() return true / false的界限: y=threshold.

以闭区间二分为例：

求最小：check(mid) == true 时更新 right = mid-1，反之更新 left = mid+1，最后返回 right+1。

求最大：check(mid) == true 时更新 left = mid+1，反之更新 right = mid-1，最后返回 left-1。

二分答案的一个难点是 check() 函数怎么写，这会涉及到贪心等技巧，可以练练贪心题单（主要是第一章节）。

二分答案模版

python
def find_answer():
    left, right = 答案的最小值, 答案的最大值
    while left < right:
        mid = left + (right - left) // 2
        if check(mid):  # check函数验证mid是否满足条件
            right = mid  # 尝试更优解
        else:
            left = mid + 1
    return left

2.1. 求最小 ​

2.2 求最大 ​

2.4 最小化最大值 ​

2.5 最大化最小值 ​

2.6 第k小/大 ​

第 k 小/大问题的通用转换方法： 这类题中k就是function中的 y，即当前数是kth个。 因为在sorted array中，nums[idx]越大,k越大。所以具备单调性，可以写成check()。

第 k 小等价于：求最小的 x，满足 ≤x 的数至少有 k 个。（注意是至少不是恰好）

第 k 大等价于：求最大的 x，满足 ≥x 的数至少有 k 个。

2.7 其他-本来具备单调性的 ​

答案范围 和 二分范围 的区别：二分范围是进行二分查找的范围，由l r的初始值决定。可能不包括答案。

此类题常见到