Sorting, Search, and Algorithm Design

sorting 与 searching 是最基础的算法操作。本文件覆盖 sorting algorithm、binary search pattern、divide and conquer、greedy algorithm、dynamic programming 与 backtracking。

• 数据结构决定可用算法，算法又依赖数据结构能力。本文件聚焦算法设计范式：面对问题时先识别应使用哪类高层策略，具体实现通常就会顺势展开。

Sorting Algorithm

• sorting 是计算机科学研究最深入的问题之一。掌握不同排序能同时建立递归、分治与复杂度分析的直觉。

Algorithm	Best	Average	Worst	Space	Stable?
Bubble sort	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	Yes
Insertion sort	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	Yes
Merge sort	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n)\)	Yes
Quick sort	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n^2)\)	\(O(\log n)\)	No
Heap sort	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(1)\)	No
Counting sort	\(O(n + k)\)	\(O(n + k)\)	\(O(n + k)\)	\(O(k)\)	Yes
Radix sort	\(O(d(n + k))\)	\(O(d(n + k))\)	\(O(d(n + k))\)	\(O(n + k)\)	Yes

• stable 表示相等元素的相对顺序在排序后保持不变。多关键字排序时这一性质非常重要。

• comparison-based sorting 的理论下界是 \(\Omega(n \log n)\)。证明基于决策树（第 13 章）：任意比较排序必须区分全部 \(n!\) 种排列，至少需要 \(\log_2(n!) = \Omega(n \log n)\) 次比较。counting sort、radix sort 之所以能突破，是因为它们不依赖元素两两比较。

Merge Sort

• 把数组对半分，递归排序左右两半，再 merge。时间始终 \(O(n \log n)\)，额外空间 \(O(n)\)。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= for stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

• 常见坑：merge 时若用 < 而不是 <=，会破坏稳定性（右半区相等元素可能跑到左半区相等元素前面）。

Quick Sort

• 选一个 pivot，将元素按“小于 pivot”和“大于 pivot”分区，再递归排序两侧。平均 \(O(n \log n)\)，最坏 \(O(n^2)\)（每次 pivot 都是最小或最大）。

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return

    pivot_idx = partition(arr, lo, hi)
    quicksort(arr, lo, pivot_idx - 1)
    quicksort(arr, pivot_idx + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]  # Lomuto: pivot is last element
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

• pivot 策略：末元素（简单但对有序输入差）、随机 pivot（期望 \(O(n \log n)\)）、median-of-three（工程中常见）。面试中建议主动说明随机 pivot 以规避最坏情况。

• 常见坑：对已排序数组用首/尾 pivot 会触发 quick sort 最坏 \(O(n^2)\)。随机化或 median-of-three 基本可避免。

Counting Sort

• 当值域是已知整数区间 \([0, k)\) 时，先统计频次再重建结果，时间 \(O(n + k)\)。它不做比较，因此可突破 \(O(n \log n)\)。

def counting_sort(arr, k):
    count = [0] * k
    for x in arr:
        count[x] += 1
    result = []
    for val in range(k):
        result.extend([val] * count[val])
    return result

• 适用条件：值域 \(k\) 不应远大于 \(n\)。若 \(k = O(n)\)，复杂度近线性；若 \(k \gg n\)（如 10 个数分布在 \([0,10^9]\)），内存浪费明显。

---

Pattern: Binary Search

• binary search 在有序数组中以 \(O(\log n)\) 查找目标，本质是不断二分搜索空间。更一般地，它是在单调条件上做搜索。

• 通用模板（最稳妥的基础版）：

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2  # avoids overflow in other languages
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1  # not found

• lower bound（第一个 \(\geq target\) 的位置）：

def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

• 常见坑：lo <= hi 与 lo < hi、hi = mid 与 hi = mid - 1 的组合决定你找的是精确值还是边界。建议用 2 元素数组手推一次校验边界。

Easy: Binary Search

• 标准题，直接套模板即可。

Medium: Search in Rotated Sorted Array

• 问题：有序数组在某点旋转，查找目标值。

• 模式：每轮至少有一半区间是有序的。先判断哪一半有序，再判断目标是否落在该半区。

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid

        # left half is sorted
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # right half is sorted
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1

    return -1

• 常见坑：nums[lo] <= nums[mid] 中的 <= 不能随意改成 <。当只剩两个元素时（lo == mid），这处判断决定逻辑是否正确。

Hard: Median of Two Sorted Arrays

• 问题：在 \(O(\log(m+n))\) 内求两个有序数组的中位数。

• 模式：在较短数组上二分“切分点”（partition），使两数组左半部分都不大于右半部分。

def find_median(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1  # ensure nums1 is shorter

    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    half = (m + n + 1) // 2

    while lo <= hi:
        i = (lo + hi) // 2          # partition point in nums1
        j = half - i                 # partition point in nums2

        left1 = nums1[i - 1] if i > 0 else float('-inf')
        right1 = nums1[i] if i < m else float('inf')
        left2 = nums2[j - 1] if j > 0 else float('-inf')
        right2 = nums2[j] if j < n else float('inf')

        if left1 <= right2 and left2 <= right1:
            # correct partition
            if (m + n) % 2 == 1:
                return max(left1, left2)
            return (max(left1, left2) + min(right1, right2)) / 2
        elif left1 > right2:
            hi = i - 1
        else:
            lo = i + 1

• 这是 binary search 经典难题。关键不是“找值”，而是“找满足条件的 partition”。

Meta-Pattern: Binary Search on Answer

• 很多题看起来不像二分，也可用“在答案空间二分”。若答案是数值，且可写单调判定函数 is_feasible(x)（例如对所有 \(x \geq\) 最优值均可行），即可对 \(x\) 二分。

• 例子：“在 \(d\) 天内运完包裹的最小运力是多少？”可在运力上二分。对每个候选运力，贪心模拟是否能在 \(d\) 天内完成。

def ship_within_days(weights, days):
    lo, hi = max(weights), sum(weights)

    while lo < hi:
        mid = (lo + hi) // 2
        # can we ship with capacity mid in <= days?
        current_load, num_days = 0, 1
        for w in weights:
            if current_load + w > mid:
                num_days += 1
                current_load = 0
            current_load += w

        if num_days <= days:
            hi = mid
        else:
            lo = mid + 1

    return lo

---

Pattern: Greedy Algorithm

• greedy 每一步都做当前最优局部选择，期望最终得到全局最优。其成立通常依赖两点：greedy choice property（局部最优可导向全局最优）和 optimal substructure（最优解由子问题最优解组成）。

Medium: Jump Game

• 问题：数组 nums[i] 表示从位置 \(i\) 最多可跳多远，判断能否到达最后位置。

def can_jump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False  # cannot reach this position
        max_reach = max(max_reach, i + jump)
    return True

• 为什么 greedy 可行：只需维护“当前最远可达位置”。如果当前位置已超过最远可达，说明必失败；否则更新最远可达即可。

Medium: Merge Intervals

• 问题：合并重叠区间。

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

• 模式：先按起点排序，再贪心合并。当前区间与最后合并区间有重叠则扩展终点，否则开启新区间。

• 常见坑：不能写 merged[-1][1] = end，要写 max(...)。因为当前区间可能完全被已有区间包含（如 [1,10] 与 [2,5]）。

---

Pattern: Dynamic Programming

• dynamic programming（DP） 将问题分解为重叠子问题，每个子问题只解一次并缓存结果。适用于具备 optimal substructure 与 overlapping subproblems 的问题。

• 两种写法：

  • top-down（memoisation）：按自然递归写法 + 缓存。
  • bottom-up（tabulation）：从最小子问题开始填表。

• 如何识别 DP：题目常问最优值（min/max）、方案数（count）或可行性（existence），且当前决策依赖历史决策。若画递归树后发现大量重复子问题，通常就是 DP。

Easy: Climbing Stairs

• 问题：共 \(n\) 级台阶，每次可走 1 或 2 级，求不同走法数。

• 这是 Fibonacci：\(f(n) = f(n-1) + f(n-2)\)。

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

• 时间 \(O(n)\)，空间 \(O(1)\)。因为每个状态只依赖前两个状态，无需完整 DP 表。

Medium: Coin Change

• 问题：给定硬币面额与目标金额，求最少硬币数。

• 状态：dp[amount] = 凑出 amount 的最少硬币数。

• 转移：dp[amount] = min(dp[amount - coin] + 1)（遍历每个 coin）。
• 初值：dp[0] = 0。

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] + 1 < dp[a]:
                dp[a] = dp[a - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1

• 常见坑：初始化必须是 float('inf')，不能是 0/ -1，否则最小值比较逻辑会失效。

Medium: Longest Common Subsequence

• 问题：给定两个字符串，求最长公共子序列长度。

• 状态：dp[i][j] = text1[:i] 与 text2[:j] 的 LCS 长度。

• 转移：若 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

Hard: 0/1 Knapsack

• 问题：给定每个物品的 weight 与 value，背包容量为 \(W\)，在不超重条件下最大化总价值。

• 状态：dp[i][w] = 前 \(i\) 个物品在容量 \(w\) 下的最大价值。

• 转移：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])（不选或选第 \(i\) 件）。

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]  # skip item i
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

• 空间优化：每行只依赖上一行，可压成 1D 数组，并让 \(w\) 从右向左迭代：

def knapsack_optimised(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):  # right to left!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

• 常见坑：1D 写法若从左到右更新，会导致同一物品被重复使用（变成 unbounded knapsack）。0/1 knapsack 必须右到左。

---

Pattern: Backtracking

• backtracking 是带剪枝的穷举：逐步构造解，一旦当前部分解不可能导向有效完整解，就立刻回退。

• 模板：

def backtrack(candidates, path, result):
    if is_solution(path):
        result.append(path[:])  # copy!
        return

    for candidate in get_candidates(path):
        if is_valid(candidate, path):
            path.append(candidate)     # choose
            backtrack(candidates, path, result)  # explore
            path.pop()                 # unchoose (backtrack)

Medium: Subsets

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

Medium: Combination Sum

• 问题：找出和为 target 的全部不重复组合（元素可重复使用）。

def combination_sum(candidates, target):
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # prune: sorted, so all further candidates are too large
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i, not i+1: reuse allowed
            path.pop()

    candidates.sort()  # sort for pruning
    backtrack(0, [], target)
    return result

• 常见坑：backtrack(i, ...) 与 backtrack(i + 1, ...) 语义不同：前者允许复用当前元素，后者不允许。这里写错是最常见 bug。

Hard: N-Queens

• 问题：在 \(n \times n\) 棋盘上放置 \(n\) 个皇后，要求互不攻击。

def solve_n_queens(n):
    result = []
    cols = set()
    pos_diag = set()  # (row + col) is constant on / diagonals
    neg_diag = set()  # (row - col) is constant on \ diagonals

    board = [['.' ] * n for _ in range(n)]

    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return

        for col in range(n):
            if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
                continue

            cols.add(col)
            pos_diag.add(row + col)
            neg_diag.add(row - col)
            board[row][col] = 'Q'

            backtrack(row + 1)

            cols.remove(col)
            pos_diag.remove(row + col)
            neg_diag.remove(row - col)
            board[row][col] = '.'

    backtrack(0)
    return result

• 关键洞察：对角线编码。/ 对角线满足 row + col 常量，\ 对角线满足 row - col 常量。用 set 维护列和对角线占用状态，可把合法性检查降到 \(O(1)\)。

---

Common Pitfalls Summary

Pitfall	Example	Fix
binary search 边界写错	lo <= hi / lo < hi 混淆	先明确 hi 是否闭区间
1D knapsack 左到右更新	同物品被重复选	0/1 knapsack 必须右到左
backtracking 不拷贝路径	result.append(path) 全部指向同对象	用 path[:] 或 path.copy()
backtrack(i) 与 backtrack(i+1) 用错	误把“可复用”写成“不可复用”	按题意选择索引推进方式
排序后未及时剪枝	继续搜索明显超限分支	排序后 if > remaining: break
DP 初值定义不清	dp[0] 错导致全表连错	先明确状态语义与 base case
greedy 直接套用无证明	局部最优不保证全局最优	至少说明贪心正确性依据
多关键字排序用不稳定算法	相等元素相对顺序被打乱	选 stable sort（如 merge sort / Python sorted）

---

Take-Home Problems（NeetCode）

Binary Search

• Binary Search — 标准模板
• Search a 2D Matrix — 矩阵拉平后二分
• Koko Eating Bananas — 对答案二分
• Search in Rotated Sorted Array — 判断有序半区
• Find Minimum in Rotated Sorted Array — 找旋转拐点
• Median of Two Sorted Arrays — partition 二分

Greedy

• Jump Game — 维护最远可达
• Jump Game II — 层次化最少跳数
• Merge Intervals — 排序 + 合并
• Insert Interval — 定位重叠区间
• Non-overlapping Intervals — 按结束时间贪心

Dynamic Programming

• Climbing Stairs — Fibonacci DP
• House Robber — 选/不选状态转移
• House Robber II — 环形数组拆两次
• Coin Change — 完全背包
• Longest Common Subsequence — 双字符串 2D DP
• Word Break — DP + 哈希加速
• Longest Increasing Subsequence — \(O(n^2)\) DP 或 \(O(n \log n)\) + binary search
• Edit Distance — 经典编辑距离 DP
• Partition Equal Subset Sum — 0/1 knapsack 变体

Backtracking

• Subsets — 全子集枚举
• Combination Sum — 可复用回溯
• Permutations — used 集合回溯
• Subsets II — 去重回溯
• Word Search — 网格回溯
• Palindrome Partitioning — 回溯 + 回文判定
• N-Queens — 约束传播