FIP W04 · 序列与查找

W4 学习记录，按原 Markdown 文件创建时间归档。

序列与查找（Sequence and Search）

根据《26FIP4 序列与查找》课件，结合原笔记整理。主线：用列表保存一组数据，在其中找最值、按值查找，并根据数据是否有序选择算法。

序列与列表

容器保存多个数据；序列中的元素有确定的先后顺序，可以按下标访问。字符串、列表、元组都是序列。这里的“有序”指位置有顺序，不等于元素已经按大小排序。

字符串是不可变序列：不能执行 s[0] = '9'。s = s + '456' 会创建新字符串，再让变量指向它；反复拼接长字符串有额外开销。

列表（list）是可变序列，可用 [] 创建，可追加和原地修改元素：

temps = []
temps.append(23.5)
temps.append(24.1)
temps.append(22.8)
temps[0] = 25.0
print(temps)  # [25.0, 24.1, 22.8]

append 是对象的方法，调用形式为 对象.方法(参数)；它原地修改列表，返回 None。

别名、拷贝与可变性

列表变量是指向列表对象的名字。b = a 使两个名字指向同一个对象，所以通过 b 修改列表也会影响 a。若要新列表，可用 a[:]、a.copy() 或 list(a)，这些都是浅拷贝：内层可变对象仍可能共享。

a = [1, 2, 3]
b = a
b[0] = 99
print(a)          # [99, 2, 3]
c = a[:]
c[0] = 0
print(a, c)       # [99, 2, 3] [0, 2, 3]

字符串不能原地改：s2 = s2 + '!' 使 s2 指向新对象，不改变原本也指向旧字符串的 s1。

下标、切片和遍历

• 下标从 0 开始；最后一项是 lst[-1]，等同于 lst[len(lst)-1]；越界引发 IndexError。
• lst[a:b] 取下标 a 至 b-1，左闭右开；lst[:] 拷贝整表；lst[::-1] 生成反序的新列表。
• lst[i] = x 原地修改列表；字符串不支持这一操作。

ids = ['A', 'B', 'C', 'D']
print(ids[1:3])   # ['B', 'C']，不含下标 3
for item in ids:               # 只需元素
    print(item)
for i, item in enumerate(ids): # 同时需要下标和元素
    print(i, item)

按下标修改元素时，可用 for i in range(len(lst))。遍历同一个列表时增删元素可能跳过或重复处理。

常用序列操作

操作	含义与注意点
a + b	连接同类序列，得到新对象，不修改原对象
a * n	重复序列，得到新对象；[1, 2] * 3 得到 [1, 2, 1, 2, 1, 2]
x in a / x not in a	判断成员；[1, 2] in [1, 2, 3] 是 False，因为列表检查的是单个元素；字符串可以检查子串
len(a)	元素个数
min(a) / max(a)	最小 / 最大元素；空序列未给默认值时会报错
sum(a)	数值元素求和；不能直接用于字符串列表

序列按字典序比较：从左到右找第一处不同元素；若已有元素都相同，则较短的序列更小。不会给较短的序列补零，例如 [2] < [2, -1] 为 True。字符串逐字符按 Unicode 码位比较，而非按汉字笔画比较。

列表还有 extend、insert、remove、pop、index、count、sort 等方法。lst.sort() 原地排序并返回 None；sorted(lst) 返回新列表。[[0]] * 3 的内层列表共享同一个对象；要独立列表可用 [[0] for _ in range(3)]。

找最值

核心是首值作种子 → 遍历剩余元素 → 遇到更优值就更新。空列表需要事先约定处理方式。

def find_max(lst):
    if not lst:
        return None
    current_max = lst[0]
    for item in lst[1:]:
        if item > current_max:
            current_max = item
    return current_max

def find_max_index(lst):
    if not lst:
        return -1
    max_idx = 0
    for i in range(1, len(lst)):
        if lst[i] > lst[max_idx]:
            max_idx = i
    return max_idx

find_max_index 遇到相同最大值时保留第一次的下标；若判断改成 >= 则保留最后一次。日常只需值时直接用 max(lst)。最坏情况下必须扫描所有元素，时间为 \(O(n)\)。

原笔记中同时寻找最大值和所有位置的写法也很实用：

def max_with_idx(sequence: list) -> tuple:
    if not sequence:
        raise ValueError('Empty sequence')
    maximum = sequence[0]
    indices = [0]
    for i in range(1, len(sequence)):
        if sequence[i] > maximum:
            maximum = sequence[i]
            indices = [i]
        elif sequence[i] == maximum:
            indices.append(i)
    return maximum, indices

max_with_idx([2, 5, 5, 1]) 得到 (5, [1, 2])：返回值是二元组，其中第二项是下标列表。

线性查找

无序列表中逐项比较目标；找到即返回下标，遍历结束还未找到则返回 -1。

def linear_search(lst: list, target) -> int:
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

def linear_search_all(lst, target):
    result = []
    for i, item in enumerate(lst):
        if item == target:
            result.append(i)
    return tuple(result)

linear_search([4, 7, 4], 4) 返回 0，即第一次出现的位置；linear_search_all 返回全部位置。元组（tuple）是不可变序列，适合表示固定的一组返回值。单元素元组写作 (1,)，(1) 只是整数。

最好情况第一项命中，时间 \(O(1)\)；目标在末尾或不存在时比较 \(n\) 次，最坏时间 \(O(n)\)。返回 -1 只是一种约定，也可设计为返回 None 或抛出异常。

函数参数与类型注解

linear_search(temps, 31.4) 按位置传参；linear_search(lst=temps, target=31.4) 按名字传参。lst: list 与 -> int 是类型注解，Python 默认不会据此在运行时强制检查。

二分查找

前提：列表已经按与目标相同的比较规则升序排列。 温度按采集时间排列，不代表温度值升序；不能直接按温度二分。若先 sorted(temps)，返回的下标对应新列表，不再自动对应原采集时间。

候选区间为闭区间 [left, right]。检查中点后，排除中点和不可能的一半：

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

在 [22.0, 23.5, 24.2, 26.8, 27.0, 28.1, 29.5, 31.4] 中找 27.0：

轮次	left	right	mid	lst[mid]	下一步
1	0	7	3	26.8	left = 4
2	4	7	5	28.1	right = 4
3	4	4	4	27.0	返回 4

left <= right 确保最后一个候选位置也被检查；写成 left < right 会漏掉单元素区间。边界更新用 mid + 1 / mid - 1，否则可能无法缩小区间。空列表初始 right = -1，直接返回 -1。有重复元素时，此实现返回某一个匹配下标，不保证第一个。

每轮候选范围约减半，最坏时间 \(O(\log n)\)，额外空间 \(O(1)\)。约一百万条已排序数据，二分查找最多约二十次比较；线性查找最坏约一百万次。

复杂度与方法选择

大 \(O\) 描述输入规模增长时算法耗时的趋势，不是具体运行秒数。列表按下标访问为 \(O(1)\)；末尾 append 通常为均摊 \(O(1)\)；按值查找和找最值是 \(O(n)\)；二分查找是 \(O(\log n)\)。

方法	数据前提	最坏查找时间	适合情况
线性查找	无需排序	\(O(n)\)	无序、小规模、只查一次
二分查找	已按目标比较规则排序	\(O(\log n)\)	已有序，或值得预先排序后多次查找

若数据无序且只查一次，先排序通常需 \(O(n\log n)\)，再二分也难以抵消准备成本；直接线性查找更合适。若必须保留原下标，排序时还需一并保存原下标。

复习时先问：数据按什么规则排序？查几次？需要值、是否存在，还是原列表下标？ 然后手推空表、单元素、首尾元素与不存在目标等边界。