B2.4.2 · Programming algorithms

B2.4.2 · 编程算法

Linear search and binary search

线性搜索与二分搜索

Two different ways to find one item in a list. Which one is actually faster depends entirely on whether the list is sorted by the thing you're searching for.

在列表中查找一个项目的两种不同方式。哪一种实际更快,完全取决于列表是否按你要搜索的内容排序。

Core for SL & HL SL 与 HL 核心内容 Typically 3–6 marks · AO3 通常 3–6 分 · AO3 Command term: construct, trace 命令词:construct(构建)、trace(追踪)

Explainer

讲解

Thornbury High's front office keeps a contact list pairing each student's name with a phone number, sorted alphabetically by name. Finding a number when you already know the name is quick. Finding out whose number a stray phone number belongs to is a completely different job, even though it's the same list.

Thornbury 高中的前台保存着一份联系人列表,将每位学生的姓名与电话号码配对,并按姓名的字母顺序排序。如果你已经知道姓名,查找号码会很快。而要查出某个不明号码属于谁,则完全是另一回事,即使用的是同一份列表。

A search algorithm finds a specific item, called the key, within a data structure. Linear search and binary search are the two required here, and they make very different assumptions about the data.

搜索算法在一个数据结构中查找一个特定的项目,称为关键值。本考纲要求的两种搜索算法是线性搜索和二分搜索,二者对数据做出的假设截然不同。

Explainer

讲解

Linear search: check every position in order

线性搜索:依序检查每一个位置

Linear search (also called sequential search) starts at the very first position and checks each one in turn, stopping only once the key is found or the list runs out.

线性搜索(也称顺序搜索)从第一个位置开始,依次检查每一个位置,直到找到关键值或列表检查完毕才停止。

Best case: the key is the very first element, found in one check. Worst case: the key is the last element, or isn't in the list at all, every single position gets checked. Time complexity: O(n). Space complexity: O(1), no extra memory grows with the list.

最佳情况:关键值恰好是第一个元素,一次检查即可找到。最坏情况:关键值是最后一个元素,或根本不在列表中,每一个位置都要被检查。时间复杂度:O(n)。空间复杂度:O(1),不随列表增长而增加额外内存。

✓

Linear search doesn't require the data to be in any particular order. It works on a sorted or unsorted list equally well, that's its whole advantage.

线性搜索不要求数据按任何特定顺序排列。无论列表已排序还是未排序,它都同样适用,这正是它的全部优势所在。

Explainer

讲解

Two ways to write it: does it stop early?

两种写法:是否提前停止?

Both versions below are linear search, and both are O(n) in the worst case, but they don't do the same amount of real work when the key is found early.

下面两个版本都是线性搜索,最坏情况下都是 O(n),但当关键值较早被找到时,它们实际完成的工作量并不相同。

Count-controlled: checks every position, regardless 计数控制:无论如何都检查每一个位置

position = -1
for i in range(len(numbers)):
    if numbers[i] == key:
        position = i

Even after finding the key on position 1 of an 8-item list, this keeps checking positions 2 through 7. Six wasted checks.

即使在一份 8 个项目的列表中,第 1 个位置就已找到关键值,这段代码仍会继续检查第 2 到第 7 个位置。白白浪费了六次检查。

Conditional loop: stops the moment it's found 条件循环:一旦找到立即停止

position = -1
i = 0
while i < len(numbers) and position == -1:
    if numbers[i] == key:
        position = i
    i = i + 1

Finds the key on position 1, and the loop's own condition (position == -1) stops it right there. No wasted checks.

在第 1 个位置找到关键值,循环自身的条件(position == -1)会立即停止循环。没有任何浪费的检查。

Explainer

讲解

Binary search: cut the remaining list in half every time

二分搜索:每次都将剩余列表一分为二

Binary search repeatedly checks the middle element and throws away the half of the list that can't possibly contain the key.

二分搜索反复检查中间元素,并舍弃列表中不可能包含关键值的那一半。

Binary search only works on sorted data 二分搜索只适用于已排序的数据

If the list isn't already in order, binary search's "throw away half" logic breaks completely, the key could be sitting in the half you just discarded. Sort the data first, or use linear search instead if sorting isn't worth the cost for a single lookup.

如果列表尚未排序,二分搜索"舍弃一半"的逻辑就会完全失效,关键值可能恰好落在你刚刚舍弃的那一半中。请先对数据排序,或者如果排序的代价对于一次查找来说不值得,就改用线性搜索。

Set a lower bound and an upper bound, the first and last valid positions in the list.

设定下界和上界,即列表中第一个和最后一个有效位置。

Calculate the middle position: mid = (lower + upper) // 2.

计算中间位置:mid = (lower + upper) // 2。

Compare the value stored at position mid with the key. If they match, the key is found. If the value at mid is too small, discard the lower half by setting lower = mid + 1. If it's too large, discard the upper half by setting upper = mid - 1.

将存储在 mid 位置的值与关键值进行比较。如果相符,则已找到关键值。如果 mid 处的值太小,则通过设置 lower = mid + 1 舍弃下半部分。如果太大,则通过设置 upper = mid - 1 舍弃上半部分。

Repeat until the key is found, or lower passes upper (meaning the key isn't in the list at all).

重复上述过程,直到找到关键值,或 lower 超过 upper(意味着关键值根本不在列表中)。

Every comparison discards roughly half of what's left, so the number of comparisons grows logarithmically. Time complexity: O(log n), far better than linear search's O(n) once the list is large.

每一次比较都会舍弃剩余部分中大约一半的内容,因此比较次数呈对数增长。时间复杂度:O(log n),一旦列表变大,远优于线性搜索的 O(n)。

Explainer

讲解

Choosing based on what you're actually searching for

根据你实际要搜索的内容来选择

The contact list is sorted by name, so the two lookups it supports are not equally fast, even though it's the exact same list.

这份联系人列表按姓名排序,因此它所支持的两种查找速度并不相同,即使用的是完全相同的一份列表。

Have a name, want the number 已知姓名,想要号码

The list is sorted by exactly this field. Binary search applies directly, O(log n).

列表正是按这个字段排序的。可以直接使用二分搜索,O(log n)。

Have a number, want the name 已知号码,想要姓名

The list is NOT sorted by number. Binary search's halving logic doesn't apply here at all, only linear search works, O(n), unless the numbers are sorted separately first.

列表并未按号码排序。二分搜索的折半逻辑在这里完全不适用,只有线性搜索有效,O(n),除非先单独对号码进行排序。

Worked example

示例讲解

Tracing a binary search

追踪一次二分搜索

The office's 8 students, sorted alphabetically. Searching for "Hunter".

前台的 8 名学生,按字母顺序排列。搜索"Hunter"。

0Ashlyn

1Bodhi

2Chiara

3Declan

4Elowen

5Flynn

6Georgia

7Hunter

lower, upper and mid, updated each round lower、upper 与 mid,每一轮都会更新 Step 1 of 4

Round 1. lower = 0, upper = 7. mid = (0 + 7) // 2 = 3, position 3 is "Declan".

第 1 轮。lower = 0,upper = 7。 mid = (0 + 7) // 2 = 3,位置 3 是 "Declan"。

"Hunter" > "Declan" alphabetically, so discard positions 0-3. New lower = mid + 1 = 4

按字母顺序,"Hunter" > "Declan",因此舍弃位置 0 到 3。新的 lower = mid + 1 = 4

Round 2. lower = 4, upper = 7. mid = (4 + 7) // 2 = 5, position 5 is "Flynn".

第 2 轮。lower = 4,upper = 7。 mid = (4 + 7) // 2 = 5,位置 5 是 "Flynn"。

"Hunter" > "Flynn", so discard positions 4-5. New lower = mid + 1 = 6

"Hunter" > "Flynn",因此舍弃位置 4 到 5。新的 lower = mid + 1 = 6

Round 3. lower = 6, upper = 7. mid = (6 + 7) // 2 = 6, position 6 is "Georgia".

第 3 轮。lower = 6,upper = 7。 mid = (6 + 7) // 2 = 6,位置 6 是 "Georgia"。

"Hunter" > "Georgia", so discard position 6. New lower = mid + 1 = 7

"Hunter" > "Georgia",因此舍弃位置 6。新的 lower = mid + 1 = 7

Round 4. lower = 7, upper = 7. mid = (7 + 7) // 2 = 7, position 7 is "Hunter". Match found.

第 4 轮。lower = 7,upper = 7。 mid = (7 + 7) // 2 = 7,位置 7 是 "Hunter"。匹配成功。

Found "Hunter" at position 7, after 4 comparisons (a plain linear search would have needed all 8).

在位置 7 找到 "Hunter",共经过 4 次比较 (普通的线性搜索则需要全部 8 次)。

Try it yourself

动手试一试

Run both searches on the same list

在同一份列表上运行两种搜索

Change target to any other name and press Run to see how many comparisons binary search needs versus linear search.

将 target 改为任意其他姓名,然后按下"运行",查看二分搜索与线性搜索各需要多少次比较。

main.py

Loading Python engine…正在加载 Python 引擎…

Output

输出

Press Run to see the output here.按下"运行"即可在此处查看输出。

Running in offline fallback mode. The full Python engine couldn't load (blocked school network, or no internet), so this console switched automatically to a small hand-written engine. It supports this page's loops and functions, but it isn't full Python.

正在以离线备用模式运行。完整的 Python 引擎无法加载(学校网络受限,或没有网络连接),因此本控制台已自动切换到一个小型的手写引擎。它支持本页的循环与函数,但并非完整的 Python。

Worked example

示例讲解

Same list, two different lookups

同一份列表,两种不同的查找

The names are sorted; the phone numbers, in the same row order, are not. Two genuinely different searches on the exact same data.

姓名已排序;而同一行顺序下的电话号码则没有排序。在完全相同的数据上进行的两种真正不同的搜索。

Position	位置	Name (sorted)
0	Ashlyn	9142
1	Bodhi	9587
2	Chiara	9203
3	Declan	9761
4	Elowen	9034
5	Flynn	9450
6	Georgia	9298
7	Hunter	9615

Looking up "Hunter"'s number: binary search on the name column, 4 comparisons (traced above). Looking up who owns 9615: the number column isn't sorted, so only linear search works, checking positions 0 through 7 in order, 8 comparisons to reach the last row.

查找 "Hunter" 的号码:对姓名列进行二分搜索,4 次比较(如上方追踪所示)。查找谁拥有 9615:号码列未排序,因此只能使用线性搜索,依次检查位置 0 到 7,需要 8 次比较才能到达最后一行。

Check your understanding

检验你的理解

A binary search has lower = 2 and upper = 9, so mid = (2 + 9) // 2 = 5. What should be compared with the search key next?

一次二分搜索中 lower = 2,upper = 9,所以 mid = (2 + 9) // 2 = 5。接下来应该与搜索关键值进行比较的是什么?

Common mistake

常见错误

Markers reported this pattern on binary search construction and tracing questions 考官在二分搜索的构建与追踪题中报告了这一模式

RecurringTwo related errors show up repeatedly: comparing the search key to the midpoint index (the number 5) instead of the value stored at that position, and computing mid once before the loop starts instead of recalculating it every time lower or upper changes.

反复出现两个相关的错误反复出现:将搜索关键值与中间下标(数字 5)进行比较,而不是与该位置存储的值比较;以及只在循环开始前计算一次 mid,而不是在 lower 或 upper 每次改变时重新计算。

Wrong, compares the index itself: if key == mid: found = True. mid is just a position number, 5. The key being searched for is a name or a number, comparing it directly to a position makes no sense.

错误,直接比较下标本身: if key == mid: found = True。mid 只是一个位置编号,5。而被搜索的关键值是一个姓名或一个号码,直接与一个位置比较毫无意义。

Wrong, mid never updates: mid calculated once, outside the while loop, then reused every round. After lower or upper changes, mid has to be recalculated from the new values, otherwise every round checks the exact same position.

错误,mid 从未更新: mid 只在 while 循环外计算一次,之后每一轮都重复使用。在 lower 或 upper 改变后,mid 必须根据新的数值重新计算,否则每一轮都会检查完全相同的位置。

✓

Right: mid = (lower + upper) // 2, recalculated inside the loop every round, then compare numbers[mid] (the value) with the key, never mid itself.

正确: mid = (lower + upper) // 2,在循环内每一轮都重新计算,然后将 numbers[mid](该值)与关键值进行比较,而不是比较 mid 本身。

Revision questions

复习题

Past-paper style. Write an answer, then reveal the marking points and mark yourself.

采用历年真题风格。写下答案,然后展开评分要点给自己打分。

Question 1 · 2 marks 第 1 题 · 2 分

[2]State the one condition the data must satisfy for binary search to work correctly.

[2]陈述数据必须满足的一项条件,才能使二分搜索正确运作。

Question 2 · 3 marks 第 2 题 · 3 分

[3]Trace a binary search for the key 9034 in the phone-number list from the worked example above, showing lower, upper and mid at each round. (Hint: the numbers must first be sorted.)

[3]在上方示例的电话号码列表中,追踪一次以 9034 为关键值的二分搜索,展示每一轮的 lower、upper 与 mid。(提示:必须先对号码进行排序。)

Question 3 · 4 marks 第 3 题 · 4 分

[4]A shop assistant needs to look up a customer's loyalty number to find their name, from a till receipt list sorted by transaction date. Explain which search algorithm is more appropriate here, and why sorting the list by loyalty number first would not necessarily be worth it for a single lookup.

[4]某店员需要从一份按交易日期排序的收银小票列表中,根据顾客的会员卡号查找其姓名。解释在这种情况下哪种搜索算法更合适,以及为什么为了一次查找而先按会员卡号对列表排序不一定值得。

Flashcards

记忆卡片

Active recall for this statement’s key terms.

针对本条考纲陈述关键术语的主动回忆练习。

Keep this statement’s practice with you

把这条考纲陈述的练习保存下来

Free account: unlock every revision question and flashcard for B2.4.2, and every other IB CS 2027 statement.

免费账户:解锁 B2.4.2 以及所有其他 IB CS 2027 考纲陈述的全部复习题和记忆卡片。