跟着NOAI考纲学Python，学完就能考，第14课

每天一个知识点，带你自学NOAI，加入我们吧~

上节课学了排序，把数据排整齐。排整齐之后干什么？当然是找东西。这节课学两种查找方法——线性查找和二分查找。学完这节，NOAI考纲里Python基础部分的知识点就全部覆盖了。

线性查找

最简单的查找方法：从第一个开始，一个一个往后看，看到目标就停。

def linear_search(lst, target):

    for i in range(len(lst)):

        if lst[i] == target:

            return i

    return -1



nums = [4, 2, 7, 1, 9, 3]

print(linear_search(nums, 7))   # 找到了，在位置2

print(linear_search(nums, 5))   # 没找到，返回-1

2
-1

逻辑很直白：遍历整个列表，找到目标就返回它的索引，全部看完都没找到就返回 -1。不管列表有没有排过序，线性查找都能用。

线性查找就像翻书一页一页找——从第一页翻到最后一页。二分查找就像查字典——翻到中间看一眼，要找的字在前面就翻前半本，在后面就翻后半本。每翻一次就排除一半。

用 in 判断

Python有更简单的写法：

nums = [4, 2, 7, 1, 9, 3]

print(7 in nums)     # 在不在？

print(nums.index(7))  # 在第几个位置？

True
2

方便，但有局限：

• in 只告诉你在不在，不告诉你在哪

• .index() 能告诉你位置，但如果元素不存在会直接报错，不像我们写的函数那样返回 -1

所以实际开发中通常先用 in 判断存不存在，再用 .index() 取位置。但考试考的是查找算法的原理，所以手写查找函数你得会。

二分查找

线性查找简单但慢——要一个一个看。如果列表已经排好序了，可以用更快的方法：二分查找。

思路：先看中间的数。如果目标比中间的小，就去左半边找；如果比中间的大，就去右半边找。每一步都把范围砍一半。

def binary_search(lst, target):

    left = 0

    right = 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



nums = [1, 3, 5, 7, 9, 11, 13]

print(binary_search(nums, 7))    # 3

print(binary_search(nums, 6))    # -1

3
-1

找 7 的过程

列表是 [1, 3, 5, 7, 9, 11, 13]，找 7：

• left=0, right=6, mid=3, lst[3]=7，正好等于目标，直接返回 3

一步就找到了。

找 6 的过程

• left=0, right=6, mid=3, lst[3]=7 > 6，目标在左边，right=2

• left=0, right=2, mid=1, lst[1]=3 < 6，目标在右边，left=2

• left=2, right=2, mid=2, lst[2]=5 < 6，目标在右边，left=3

• left=3 > right=2，循环结束，返回 -1

7个数，3步就确定找不到了。

二分查找有多快

具体比较一下：

• 1000个数据，线性查找最多找 1000 次

• 1000个数据，二分查找最多找 10 次（因为 2的10次方 = 1024 > 1000）

• 100万个数据，线性查找最多 100万 次，二分查找最多 20 次

差距非常大。这就是为什么"先排序再二分查找"是很多算法的基础操作。

但要注意：二分查找只能用在已经排好序的列表上。如果列表是乱序的，要么先排序再二分，要么直接用线性查找。

实战：排序 + 查找

把上节课和这节课学的组合起来——先排序，再二分查找：

def binary_search(lst, target):

    left = 0

    right = 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



scores = [78, 92, 55, 88, 41, 67, 95]

scores.sort()  # 先排序

print("排好序：", scores)



pos = binary_search(scores, 88)

if pos != -1:

    print("88分在位置", pos)

else:

    print("没找到88分")

排好序： [41, 55, 67, 78, 88, 92, 95]
88分在位置 4

这就是排序和查找的经典组合：先用 .sort() 排好序，再用二分查找快速定位。

易错点

错误1二分查找忘了排序

二分查找只在排好序的列表上才有效。对一个乱序列表用二分查找，结果完全不可靠：

nums = [9, 3, 7, 1, 5]  # 没排序！

print(binary_search(nums, 3))  # 结果可能是错的

用二分查找之前，先确认列表已经排好序。

错误2mid 的计算用 / 不用 //

mid = (left + right) / 2   # 错！得到3.0，浮点数不能当索引

mid = (left + right) // 2  # 对！得到3，整数才能当索引

/ 是普通除法，结果是浮点数；// 是整除，结果是整数。列表索引必须是整数，所以必须用 //。

动手试试

自己先想，想完了去香农平台上写代码跑一遍验证。

nums = [8, 3, 5, 1, 9, 2]

print(binary_search(nums, 5))

去平台上手写代码

查找是算法入门的核心知识点。回顾一下：

• 线性查找 — 逐个比较，简单但慢

• 二分查找 — 每次排除一半，快但必须先排序

• in 和 index() — Python的查找捷径

• 1000个数据线性查 1000 次，二分只查 10 次

这篇文章讲的是香农NOAI学习平台"Python基础"模块的第十四课。平台上有更多的练习题，写完代码点运行，对不对立刻就知道。

香农NOAI学习平台
地址：shannon.arpa.school
微信扫码登录就能用，免费。
找到「Python基础」→「查找」，从第一道题开始写。

到这里，NOAI考纲里Python基础部分的知识点全部讲完了。从第一行 print 到现在的二分查找，14节课覆盖了：变量、数据类型、输入输出、条件判断、循环、列表、函数、字典、元组、字符串、模块、排序、查找。

接下来的课程会进入数据处理和AI——用NumPy、Pandas处理数据，用Matplotlib画图，这些是NOAI考试第二轮的核心内容。