信息学奥赛基础：算法启蒙与竞赛入门

会写代码不等于会解算法题。写代码是把已知的逻辑翻译成程序，解算法题是面对一个从未见过的问题，自己想出解决步骤，再翻译成代码。后者多了一个最关键的环节：设计解法。

比如题目说"给你一列数字，找出其中最大的那个"。初学者可能直接写 if 一个一个比，但学过算法之后会想：需要遍历整个列表吗？如果列表已经排好序，最大值是不是直接取最后一个？不同的选择对应不同的时间效率——算法就是在各种解法中选最适合的那个。

算法思维的三个核心问题：这个问题的输入是什么？输出是什么？用什么步骤从输入走到输出？把这三个问题想清楚，代码只是最后一步表达。

数组是竞赛题里最常用的数据结构。你可以把它理解成一排连续的盒子，每个盒子里放一个数字，用编号（下标）区分。在 Python 里，列表就是数组：

nums = [3, 7, 2, 9, 4]
print(nums[0])   # 输出 3（第一个元素）
print(nums[3])   # 输出 9（第四个元素）

下标从 0 开始是很多初学者容易犯的错——第一个元素是 nums[0] 不是 nums[1]。这个习惯一旦养成就好，改不过来就是无数个差一错误。

有了数组，配合 for 循环就能做很多事：遍历求和、找最大值、统计个数。下面这段代码找出数组里的最大值：

nums = [3, 7, 2, 9, 4]
max_val = nums[0]
for i in range(1, len(nums)):
    if nums[i] > max_val:
        max_val = nums[i]
print("最大值是", max_val)

逻辑很直白：先假设第一个元素是最大的，然后依次和后面每个元素比，遇到更大的就更新。这种"打擂台"的思路是很多算法题的基础。

查找是最基础的算法问题：给你一个数字，问它在不在列表里。最笨的办法是从第一个元素开始一个个找，这叫顺序查找。列表有 1000 个元素，最坏要比 1000 次。

如果列表已经排好序了，就可以用二分查找：每次看中间那个元素，比目标大就往左半边找，比目标小就往右半边找。每次都把搜索范围砍一半，1000 个元素只要比 10 次左右就能找到。

nums = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
left = 0
right = len(nums) - 1

while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
        print("找到了，位置在", mid)
        break
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
else:
    print("没找到")

二分查找的代码不长，但边界条件很容易写错：left 和 right 什么时候加 1、什么时候减 1、循环什么时候停。这是竞赛入门必练的经典题，一定要自己手写几遍。

方法	前提	1000 个元素最坏比较次数
顺序查找	无	1000 次
二分查找	列表已排序	约 10 次

排序是竞赛题里出现频率最高的操作之一。冒泡排序是最容易理解的排序算法：反复遍历列表，每次比较相邻两个元素，如果顺序不对就交换。一轮下来，最大的元素会像气泡一样"浮"到最后面。

nums = [5, 2, 8, 1, 9]
n = len(nums)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if nums[j] > nums[j + 1]:
            nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(nums)  # 输出 [1, 2, 5, 8, 9]

这段代码里两层循环：外层跑 n-1 轮，内层每轮比较相邻元素。每做完一轮，最后面的 i 个元素已经排好了，不用再比。

冒泡排序效率不高——n 个元素要比大约 n 的平方次，但它逻辑简单，是理解排序过程的最佳起点。等孩子手写几遍冒泡排序之后，再去学选择排序、插入排序，最后到快速排序，会非常顺。