| English | 释义 | 拼音 |
|---|---|---|
| algorithm/ˈælɡərɪθəm/ | 算法 | suàn fǎ |
| flowchart/ˈfləʊtʃɑːt/ | 流程图 | liú chéng tú |
| pseudocode/ˈsuːdəʊkəʊd/ | 伪代码 | wěi dài mǎ |
| tracing/ˈtreɪsɪŋ/ | 追踪 | zhuī zōng |
| binary search/ˈbaɪnəri sɜːtʃ/ | 二分查找 | èr fēn chá zhǎo |
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
| efficiency/ɪˈfɪʃənsi/ | 效率 | xiào lǜ |
Say which inputs the procedure must handle
- An algorithm 算法 describes unambiguous steps for a task. A procedure solving a stated finite task must terminate and give the correct result for every allowed input.
- A successful trace on one input shows that case, not a proof for all inputs. Boundary and empty-input cases can expose errors that a typical example misses.
哪些条件是序列成为算法所必需的?全选适用项。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
解决所述有限任务的过程需要明确的步骤、正确的结果以及在允许输入下终止。伪代码和流程图是表示形式,而非必须使用特定编程语言的要求。
Represent choices and updates clearly
- A flowchart 流程图 uses a decision diamond, process rectangle, input/output parallelogram and start/stop terminal, connected by directed flow arrows.
- Pseudocode 伪代码 describes the steps without requiring one implementation language. State assignment meaning, index origin, loop bounds and branch conditions before tracing.
![Binary search for 7 in [1, 3, 5, 7, 9, 11]: first the middle index 2 holds 5 < 7, so go right; second, the middle index 4 holds 9 > 7, so go left; third, index 3 holds 7, found after three comparisons under this convention](/learn-media/gac_mathematics/assets/0404-binary-search-steps.png?v=1794647931)
将每个流程图形状与其含义匹配。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
按给定要求使用过程矩形、判断菱形及开始/结束终端;输入/输出通常以平行四边形表示。请标注判断分支和流程方向。
Record the actual variable values
- Tracing 追踪 follows the stated updates in order. A temporary variable may preserve a value that would otherwise be overwritten.
- Show low, high, middle and compared value for a binary search; show every changed variable for an arithmetic loop. Judge what the procedure does, not only its intended purpose.
A specified binary-search convention. Use zero-based inclusive bounds and floor of their average for the middle. Searching for 7 in [1,3,5,7,9,11] compares index 2/value 5, index 4/value 9, then index 3/value 7. The comparison count is three under this convention.
线性搜索对比二分搜索
减半优于逐一检查,列表越长差距越大。
使用从零开始的包含性边界和 floor((low+high)/2),二分查找在 [1,3,5,7,9,11] 中查找 7 需要进行多少次比较?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
中间索引依次为 2、4,然后是 3,对应值分别为 5、9 和 7。按照指定约定,共进行三次比较。
Compare work under its assumptions
- A linear search 线性查找 can stop early but may inspect all n items. A binary search repeatedly halves a sorted search range and needs consistent bound updates.
- Efficiency 效率 describes how required work scales with input size under a defined model. Sorting first has its own cost; an unsorted input cannot rely on binary search's ordering guarantee.
对于一个已排序的百万项列表,二分查找在最坏情况下大约需要进行多少次中间值比较?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
每次比较都将剩余搜索范围减半;对于百万有序元素,约需 20 次比较即可。此计算不包含预先排序的任何开销。
二分搜索适用于无序列表,只是更慢。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
若缺乏所需的有序性,丢弃一半数据可能会遗漏目标项。某些情况可能碰巧成功,但无法保证正确性。
Check zero and the last allowed index. Sheet 4.4 examines a sum loop using i less than n, which misses the last term. Its Euclidean trace also explains termination: each positive divisor is replaced by a smaller nonnegative remainder until zero is reached.