二分查找和归并排序如何用于 GCSE?

如果你在复习 GCSE 计算机科学的算法，四个名字会一再出现：线性搜索、二分查找、冒泡排序和归并排序。考试委员会喜欢让你手工追踪这些算法、判断运行时间，或填写缺失的伪代码行。这里是考试及以后真正重要的内容。

线性搜索：基础

线性搜索逐个检查列表中的每一项，直到找到目标或到达末尾。就是这样。

for i = 0 to length(list) - 1
    if list[i] == target then
        return i
return -1

最坏情况下，你检查每个元素，所以复杂度是 O(n)。最好情况下，目标在第一位，所以是 O(1)。考官喜欢让你同时说出两个。线性搜索适用于无序数据，这是它相比二分查找的唯一真正优势。

二分查找：容易混淆的那个

二分查找只在有序列表上工作。你将目标与中间项比较。如果目标更小，丢弃上半部分；如果更大，丢弃下半部分。重复直到找到或没有项了。

low = 0
high = length(list) - 1
while low <= high
    mid = (low + high) / 2
    if list[mid] == target then
        return mid
    else if list[mid] < target then
        low = mid + 1
    else
        high = mid - 1
return -1

这是 O(log n)，这就是为什么在大数据集上快得多。搜索一百万项的有序列表，线性搜索可能需要多达一百万次比较；二分查找需要约 20 次。考官常给你一个列表，比如 16 个数字，让你追踪哪些索引被检查过——用纸笔练习这个，不只是在脑子里。

冒泡排序：简单但缓慢

冒泡排序反复遍历列表，如果相邻项顺序错了就交换它们。每次完整遍历把最大的未排序项推到末尾的正确位置。

for i = 0 to length(list) - 1
    for j = 0 to length(list) - 2 - i
        if list[j] > list[j+1] then
            swap(list[j], list[j+1])

最坏情况是 O(n²)——对于每个元素，你可能再次扫描几乎整个列表。它在实际软件中很少使用，因为在大数据上很慢，但考官喜欢它，因为手工追踪是可操作的，它清楚地展示了重复遍历和交换的思想。知道如何在追踪表中计算比较和交换的数量；这是常见的评分标准项。

归并排序：分治法

归并排序反复将列表分成两半，直到每个子列表只有一项，然后按排序顺序将这些子列表合并回来。

function mergeSort(list)
    if length(list) <= 1 then
        return list
    mid = length(list) / 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

合并步骤比较每一半的首项并选择较小的，重复直到两半都用完。这给出 O(n log n)，除了极小的列表外都大大优于冒泡排序。GCSE 问题有时让你画出分割和合并图——一个树形状，显示列表向下分割然后重新合并。为一个 8 项的列表练习画这个，这样在考试条件下你能快速完成。

考官实际测试什么

大多数评分标准希望你能够：

• 逐步追踪一个算法，写下每次遍历或比较后列表的状态。
• 用 Big O 术语陈述时间复杂度，或至少用词描述它(