Search Algorithms Explained | 搜索算法解析

📚 Search Algorithms Explained | 搜索算法解析

In computer science, searching is a fundamental operation that allows programs to locate specific data within a collection. Whether finding a contact in a phone book, checking for a product in an online store, or locating a record in a database, efficient search algorithms are critical to software performance. For GCSE Edexcel Computer Science, you need to master two core search techniques: linear search and binary search. This guide breaks down their logic, pseudocode, efficiency, and common exam applications, equipping you with the knowledge to tackle any search-related question confidently.

在计算机科学中，搜索是一项基础操作，它使程序能够在数据集合中找到特定的条目。无论是在通讯录中查找联系人、在网店中搜索商品，还是在数据库中定位记录，高效的搜索算法都对软件性能至关重要。在 GCSE Edexcel 计算机科学考试中，你需要掌握两种核心搜索技术：线性搜索和二分搜索。本指南将详细解析它们的逻辑、伪代码、效率以及常见的考试应用，帮助你自信应对任何与搜索相关的问题。

1. What is a Search Algorithm? | 什么是搜索算法？

A search algorithm is a step-by-step procedure designed to retrieve one or more data items from a data structure. It accepts a list of items and a target value, then returns the position (index) of the target if it exists, or a message indicating it is not present. Search algorithms underpin many everyday applications, including autocomplete, lookup functions in spreadsheets, and database queries. In GCSE Edexcel Computer Science, the focus is on two contrasting strategies: serial (linear) search and interval (binary) search.

搜索算法是一种设计用于从数据结构中检索一个或多个数据项的分步操作过程。它接收一个项目列表和一个目标值，如果目标存在则返回其位置（索引），否则返回一条表示未找到的消息。搜索算法是许多日常应用的基础，包括自动完成、电子表格中的查找函数和数据库查询。在 GCSE Edexcel 计算机科学中，重点学习两种截然不同的策略：串行（线性）搜索和区间（二分）搜索。

Algorithms are evaluated by their correctness and efficiency. Correctness means the algorithm always yields the expected result, while efficiency relates to how many steps it takes as the input size grows. Search algorithms provide an excellent introduction to algorithmic thinking, as they require you to construct precise sequences of operations, handle edge cases, and reason about performance using Big O notation.

算法通过其正确性和效率来评估。正确性意味着算法总能产生预期的结果，而效率则涉及随着输入规模的增大，算法需要执行多少步操作。搜索算法是学习算法思维的绝佳起点，因为它们要求你构建精确的操作序列、处理边缘情况，并使用大 O 表示法分析性能。

2. Linear Search: Step-by-Step | 线性搜索：逐步解析

Linear search, also known as sequential search, is the simplest approach: check every element one by one from the beginning until the target is found or the list ends. Imagine you have a stack of exam papers arranged randomly, and you need to find a student named “Alice”. You would examine each paper in turn: first, second, third, and so on, until “Alice” appears or you run out of papers. Linear search does not require the data to be sorted; it works on any list, making it very versatile.

线性搜索，也称为顺序搜索，是最简单的方法：从开头开始逐个检查每个元素，直到找到目标或列表结束。想象你有一叠随机排列的试卷，需要找出一位名叫“Alice”的学生。你会依次检查每一份：第一份、第二份、第三份……直到“Alice”出现或试卷耗尽。线性搜索不要求数据已排序，它适用于任何列表，因此非常通用。

The algorithm can be traced using an index variable. Start with index = 0. Compare the item at that index with the target. If they match, return index. If not, increment index by 1 and repeat. If index exceeds the last valid position without a match, the target is not in the list. Linear search is intuitive, but for large lists it may become slow because, in the worst case, you examine every single element.

该算法可以用一个索引变量来追踪。从索引 = 0 开始，将位于该索引处的元素与目标值进行比较。如果匹配，则返回该索引；否则，索引加 1 并重复此过程。如果索引超过了最后一个有效位置仍未找到匹配项，则目标不在列表中。线性搜索直观易懂，但对于大型列表，它可能变得很慢，因为在最坏的情况下，你需要检查每一个元素。

3. Pseudocode for Linear Search | 线性搜索的伪代码

Edexcel expects you to read, interpret, and write pseudocode for standard algorithms. Below is a typical linear search pseudocode using a zero-indexed array. The example returns the index of the first occurrence; you might also see versions returning a Boolean value or counting occurrences.

Edexcel 期望你能阅读、解释并编写标准算法的伪代码。以下是一个使用零索引数组的典型线性搜索伪代码。该示例返回第一次出现处的索引；你也可能遇到返回布尔值或统计出现次数的版本。

FUNCTION linearSearch(arr, target)
  FOR i ← 0 TO LEN(arr) – 1
    IF arr[i] = target THEN
      RETURN i
    ENDIF
  ENDFOR
  RETURN -1
ENDFUNCTION

The pseudocode uses a FOR loop to traverse the array. When arr[i] equals target, the function immediately returns the current index i. If the loop completes without a return, the algorithm returns -1, a conventional way to signal “not found”. Edexcel pseudocode often uses keywords like OUTPUT or PRINT for other variations, but the core logic remains identical.

该伪代码使用 FOR 循环遍历数组。当 arr[i] 等于目标值时，函数立即返回当前索引 i。如果循环结束时仍无返回，则算法返回 -1，这是表示“未找到”的常规约定。Edexcel 的伪代码常在其它变体中使用 OUTPUT 或 PRINT 等关键字，但核心逻辑保持不变。

4. Binary Search: Step-by-Step | 二分搜索：逐步解析

Binary search is a far more efficient algorithm but comes with a strict requirement: the data must be sorted in ascending (or descending) order. It repeatedly divides the search interval in half, comparing the middle element with the target. If the middle element matches the target, the search ends. If the target is smaller, the search continues in the lower half; if larger, in the upper half. This halving eliminates large portions of the list with each step, drastically reducing the number of comparisons.

二分搜索是一种效率高得多的算法，但它有一个严格的要求：数据必须按升序（或降序）排列。它反复将搜索区间一分为二，将中间元素与目标值进行比较。如果中间元素与目标匹配，搜索结束。如果目标值较小，则继续在下半部分搜索；如果较大，则在上半部分搜索。这种对半分割的方式每一步都能排除列表的大部分区域，大幅减少了比较次数。

Think of searching for a word in a dictionary. You do not start at page 1 and read every entry; instead, you open approximately to where you think the word might be, then adjust forward or backward based on alphabetical order. Binary search mirrors this intuition digitally. For a sorted list of 1,000,000 items, binary search locates any target in at most about 20 comparisons, whereas linear search might need all 1,000,000.

不妨想象在字典中查找一个单词。你不会从第一页开始逐词阅读，而是根据字母顺序大致翻到某个位置，然后向前或向后调整。二分搜索在数字世界中模拟了这种直觉。对于一个包含 1,000,000 个元素的已排序列表，二分搜索最多只需大约 20 次比较即可定位任何目标，而线性搜索可能需要全部 1,000,000 次。

5. Pseudocode for Binary Search | 二分搜索的伪代码

Binary search uses two pointers: low and high, marking the boundaries of the search area. A midpoint index is calculated, and based on the comparison, either found, or adjust low/high. Below is the standard iterative pseudocode suitable for the Edexcel specification.

二分搜索使用两个指针：low 和 high，标记搜索区域的边界。计算出一个中间点索引，通过比较结果，要么找到目标，要么调整 low 或 high 的值。下面是适合 Edexcel 考试大纲的标准迭代伪代码。

FUNCTION binarySearch(arr, target)
  low ← 0
  high ← LEN(arr) – 1
  WHILE low ≤ high DO
    mid ← (low + high) DIV 2
    IF arr[mid] = target THEN
      RETURN mid
    ELSE IF arr[mid] < target THEN
      low ← mid + 1
    ELSE
      high ← mid – 1
    ENDIF
  ENDWHILE
  RETURN -1
ENDFUNCTION

The DIV operator performs integer division, discarding any remainder to give a valid array index. When arr[mid] < target is true, the target must lie in the upper segment, so low is adjusted. Conversely, if arr[mid] > target, high is reduced. The loop continues until low exceeds high, at which point the target is confirmed absent. This algorithm is often tested in exam trace tables, requiring you to step through each variable update carefully.

DIV 运算符进行整数除法，丢弃任何余数以获得有效的数组索引。当 arr[mid] < target 成立时，目标必定位于上半段，因此调整 low。反之，如果 arr[mid] > target，则减小 high。循环持续进行，直到 low 超过 high，此时确认目标不存在。考试中常常通过跟踪表来测试该算法，要求你仔细追踪每一步的变量更新。

6. Comparing Linear and Binary Search | 线性搜索与二分搜索的比较

Both algorithms solve the same problem but differ dramatically in their prerequisites, performance, and implementation complexity. The table below summarises the key distinctions you need to remember for your GCSE exams.

这两种算法解决相同的问题，但在前提条件、性能和实现复杂度上存在显著差异。下表总结了你需要为 GCSE 考试牢记的关键区别。

Feature	Linear Search	Binary Search
Data requirement	Unsorted or sorted	Must be sorted
Best-case time	O(1) – target at first position	O(1) – target at midpoint
Worst-case time	O(n)	O(log n)
Space complexity	O(1) – uses few variables	O(1) for iterative version
Simplicity	Very easy to implement	Slightly more complex
Works on linked lists?	Yes	Not efficiently; needs random access

Linear search is the go-to choice when data is unsorted, when the list is small, or when the list structure (like a linked list) does not support direct index access. Binary search shines on large, sorted arrays, where its O(log n) time complexity provides a massive performance advantage.

当数据未排序、列表较小，或列表结构（如链表）不支持直接索引访问时，线性搜索是首选。二分搜索则适用于大型、已排序的数组，其 O(log n) 的时间复杂度带来了巨大的性能优势。

7. Efficiency and Big O Notation | 效率与大O表示法

Big O notation describes the upper bound of an algorithm’s growth rate, telling us how the number of basic operations scales with input size n. For linear search, in the worst case every element is compared once, so it is O(n). Binary search repeatedly halves the problem, which yields a logarithmic relationship; the worst-case number of comparisons is proportional to log₂n, written O(log n).

大 O 表示法描述了算法增长率的上限，告诉我们基本操作的次数如何随输入规模 n 变化。对于线性搜索，最坏情况下每个元素都比较一次，因此是 O(n)。二分搜索不断将问题减半，这产生对数关系；最坏情况下的比较次数与 log₂n 成正比，记为 O(log n)。

Consider a list of 1024 elements. Linear search could need up to 1024 comparisons. Binary search will need at most log₂1024 = 10 comparisons. For 1,048,576 items, the contrast is even starker: 1,048,576 versus 20. This dramatic difference is why binary search is preferred for large datasets, but the sorting requirement adds a preprocessing cost. Understanding these complexity classes lets you justify algorithm choice in exam scenarios.

考虑一个包含 1024 个元素的列表。线性搜索最多需要 1024 次比较，而二分搜索至多只需 log₂1024 = 10 次。对于 1,048,576 个元素，对比更为惊人：1,048,576 次对比 20 次。如此巨大的差异解释了为何二分搜索被优先用于大规模数据集，但排序要求增加了预处理成本。理解这些复杂度类别能让你在考试场景中合理解释算法的选择。

8. When to Use Each Algorithm | 何时使用每种算法

Choosing the right search algorithm depends on context. Linear search is best when:

The list is unsorted and sorting would be too expensive or unnecessary.
You need to find all occurrences of a target (by not stopping at the first match).
The data structure is a linked list or file where random access is impossible.
The list is very small, so the overhead of binary search logic is not justified.

Binary search is the superior choice when:

The data is already sorted or can be sorted once and searched many times.
The collection supports direct indexing (e.g. arrays, Python lists).
Performance is critical and n is large (e.g. searching in a database index).
You need the fastest possible search time for repeated queries.

选择正确的搜索算法取决于上下文。线性搜索在以下情况最为合适：

列表未排序，且排序代价过高或不必要。
你需要找到目标的所有出现位置（而不是在第一次匹配后就停止）。
数据结构是链表或文件，无法实现随机访问。
列表非常小，二分搜索逻辑的开销并不合理。

二分搜索在以下情况是更优选择：

数据已经排序，或可以排序一次然后反复搜索。
集合支持直接索引（例如数组、Python 列表）。
性能至关重要且 n 很大（例如在数据库索引中搜索）。
你需要为重复查询提供尽可能快的搜索速度。

9. Common Pitfalls and Exam Tips | 常见错误与考试技巧

Many marks are lost due to small mistakes in pseudocode or misconceptions about binary search. A frequent error is forgetting to sort the list before applying binary search – the algorithm will fail to produce correct results if the data is unsorted. In pseudocode, using integer division incorrectly for the midpoint (e.g. forgetting DIV and using ordinary division) leads to fractional indices that break the algorithm. When tracing, students sometimes miscompute the new low or high, setting low = mid instead of mid + 1, causing infinite loops.

许多失分源自伪代码中的小错误或对二分搜索的误解。一个常见错误是应用二分搜索前忘记对列表排序——如果数据未排序，算法将无法产生正确结果。在伪代码中，错误地使用普通除法代替整数除法来计算中间点，会导致产生小数索引从而破坏算法。在跟踪执行时，学生有时会错误地设定新的 low 或 high，将 low = mid 而非 mid + 1，导致死循环。

Exam tips: always label the low, mid, high variables clearly in trace tables. Check whether the question expects a 0‑based or 1‑based index. For linear search, be clear about whether you are returning the position or the value. Practice writing both algorithms without prompts, then check against the official pseudocode guide. When asked to compare algorithms, structure your answer around data requirements, efficiency (using Big O), and suitability for different scenarios – not just a description of the steps.

考试技巧：在跟踪表中始终清晰地标注 low、mid、high 变量。检查题目期望的是基于 0 还是基于 1 的索引。对于线性搜索，要明确你是返回位置还是值。练习在没有提示的情况下编写两种算法，然后对照官方伪代码指南进行检查。当被要求比较算法时，你的答案应围绕数据要求、效率（使用大 O 表示法）以及不同场景的适用性来组织——而不仅仅是描述步骤。

10. Practice and Exam Application | 练习与考试应用

GCSE Edexcel questions often present a partially filled trace table or ask you to complete the pseudocode for a search on a specific array. You may also be given a scenario – such as searching a music playlist or a school database – and need to justify why linear or binary search is more appropriate. Some 6-mark questions require you to fully outline an algorithm with its steps, advantages, and disadvantages, so being fluent in the key terminology (sorted, efficiency, logarithmic, O(n), etc.) is essential.

GCSE Edexcel 考题常常给出一个部分填写的跟踪表，或者要求你补全在特定数组上执行搜索的伪代码。你也可能被给到一个场景——比如搜索音乐播放列表或学校数据库——并需要说明为什么线性搜索或二分搜索更合适。一些 6 分题要求你完整概述一种算法，包括其步骤、优点和缺点，因此能流利使用关键术语（排序、效率、对数、O(n) 等）至关重要。

Sample quick-fire scenarios: 1) A teacher takes a register from a list of names that is alphabetically sorted; which search should be used for quick lookup? (Binary). 2) A small to‑do list app stores five tasks in the order they were entered; which search is simplest? (Linear). 3) An online library catalogue contains 500,000 titles sorted by ISBN; which algorithm minimises server load? (Binary). Being able to reason about such cases demonstrates deep understanding.

示例快速情境题：1) 老师从一个按字母排序的姓名列表中登记出勤，应该使用哪种搜索以实现快速查找？（二分搜索）。2) 一个小的待办事项应用以录入顺序存储了五个任务，哪种搜索最简单？（线性搜索）。3) 一个在线图书馆目录包含按 ISBN 排序的 50 万册书目，哪种算法能最小化服务器负载？（二分搜索）。能够对此类案例进行推理，表明你有深刻的理解。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Search Algorithms Explained | 搜索算法解析