python 算法模板

以下是常见的Python算法模板：

1. 二分搜索（实数搜索、整数搜索）

def check(k):
    # 根据题目要求（难点），返回True或False

# 实数搜索
def bin_float_search(l, r):
    while r - l > 0.001:  # 精度
        mid = (l + r) / 2
        if check(mid):
            l = mid
        else:
            r = mid
    mid = (l + r) / 2
    return mid

# 整数搜索
def bin_int_search(l, r):
    while l < r:
        mid = (l + r) >> 1
        if check(mid):
            r = mid
        else:
            l = mid + 1
    return mid

2. 前缀和、差分数组
前缀和是指数组中每个位置前面所有元素的和，差分数组是指数组中每个位置与前一个位置的差值。

# 前缀和
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
    prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]

# 差分数组
diff = [0] * n
for i in range(1, n):
    diff[i] = nums[i] - nums[i - 1]