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

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

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

线性查找

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

deflinear_search(lst, target):foriinrange(len(lst)):iflst[i] == target:returnireturn -1nums = [4, 2, 7, 1, 9, 3]print(linear_search(nums, 7))   # 找到了，在位置2print(linear_search(nums, 5))   # 没找到，返回-1

2-1

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

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

用 in 判断

Python有更简单的写法：

nums = [4, 2, 7, 1, 9, 3]print(7innums)     # 在不在？print(nums.index(7))  # 在第几个位置？

True2

方便，但有局限：

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

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

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

二分查找

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

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

defbinary_search(lst, target):left = 0right = len(lst) - 1whileleft <= right:mid = (left + right) // 2iflst[mid] == target:returnmideliflst[mid] < target:left = mid + 1else:right = mid - 1return -1nums = [1, 3, 5, 7, 9, 11, 13]print(binary_search(nums, 7))    # 3print(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 次

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

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

实战：排序 + 查找

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

defbinary_search(lst, target):left = 0right = len(lst) - 1whileleft <= right:mid = (left + right) // 2iflst[mid] == target:returnmideliflst[mid] < target:left = mid + 1else:right = mid - 1return -1scores = [78, 92, 55, 88, 41, 67, 95]scores.sort()  # 先排序print("排好序：", scores)pos = binary_search(scores, 88)ifpos != -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考试第二轮的核心内容。