Search Algorithms: Linear and Binary Search | 搜索算法考点精讲

📚 Search Algorithms: Linear and Binary Search | 搜索算法考点精讲

Searching is one of the most fundamental operations in computer science, allowing programs to locate specific data within a collection. In the Edexcel A-Level Computer Science specification, you are expected to understand, implement and compare two core search algorithms: linear search and binary search. Mastery of these algorithms is essential for both the algorithm analysis topic and as a building block for more advanced data structures.

搜索是计算机科学中最基本的操作之一，它使程序能够在数据集合中定位特定元素。在 Edexcel A-Level 计算机科学考试大纲中，你需要理解、实现并比较两种核心搜索算法：线性搜索和二分搜索。掌握这些算法对于算法分析专题以及作为更高级数据结构的基础都至关重要。

1. Introduction to Searching | 搜索算法简介

A search algorithm is a step-by-step procedure used to retrieve an element from a data structure. The goal is usually to find the index of a target value or to confirm that the value does not exist. The efficiency of a search algorithm directly impacts the performance of software, especially when handling large datasets.

搜索算法是一种用于从数据结构中检索元素的分步过程。其目标通常是找到目标值的索引，或确认该值不存在。搜索算法的效率直接影响软件的性能，尤其是在处理大规模数据集时。

Edexcel focuses on two contrasting approaches: linear search, which works on any list, and binary search, which requires a sorted list but is far more efficient on larger collections. Understanding when to apply each is a key exam skill.

Edexcel 重点考查两种截然不同的方法：线性搜索适用于任意列表，而二分搜索需要有序列表，但在较大集合上效率更高。理解何时使用每种方法是关键的考试技能。

2. Linear Search Algorithm | 线性搜索算法

Linear search, also called sequential search, examines every element in a list one by one starting from the first position. It continues until a match is found or the end of the list is reached. No prior ordering of the data is required.

线性搜索，又称顺序搜索，从第一个位置开始逐一检查列表中的每个元素。它会一直进行，直到找到匹配项或到达列表末尾。数据无需事先排序。

The algorithm is intuitive and easy to code, making it a good choice for small or unsorted datasets. In the worst case it must look at every element, so its efficiency is proportional to the number of items.

该算法直观且易于编码，因此非常适用于小型或未排序的数据集。在最坏情况下，它必须检查每一个元素，其效率与元素的数量成正比。

3. Linear Search Pseudocode and Walkthrough | 线性搜索伪代码与过程演示

The pseudocode below describes a linear search that returns the index of the target if found, or -1 if the target is not in the array.

下面的伪代码描述了一种线性搜索：如果找到目标，则返回其索引；如果目标不在数组中，则返回 -1。


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

As an example, suppose we have the array [3, 8, 2, 7, 5] and target = 7. The loop checks index 0 (3), index 1 (8), index 2 (2) and at index 3 finds 7, returning 3. If target were 10, the loop would traverse all five elements and then return -1.

例如，假设我们有一个数组 [3, 8, 2, 7, 5]，目标值 target = 7。循环检查索引 0 (3)、索引 1 (8)、索引 2 (2)，在索引 3 处找到 7，返回 3。如果 target 为 10，循环将遍历全部五个元素，然后返回 -1。

This simple behaviour illustrates why linear search is reliable but potentially slow for long lists, as the number of comparisons grows linearly with the list size.

这一简单行为说明了为什么线性搜索可靠，但对于长列表可能较慢，因为比较次数随列表大小线性增长。

4. Analysing Linear Search Complexity | 分析线性搜索复杂度

The time complexity of linear search is expressed in Big O notation. In the best case the target is at the very first position, requiring just one comparison — O(1). The average and worst cases both require checking roughly half or all the elements, giving O(n).

线性搜索的时间复杂度用大 O 表示法表示。在最佳情况下，目标正好在第一个位置，仅需一次比较 —— O(1)。平均和最坏情况都需要检查大约一半或全部元素，因此为 O(n)。

Case	Complexity	Scenario
Best	O(1)	Target at index 0
Average	O(n)	Target somewhere in the middle
Worst	O(n)	Target not present or at the end

The space complexity is O(1) because the algorithm uses only a fixed number of variables regardless of input size. This makes linear search memory efficient.

空间复杂度为 O(1)，因为无论输入大小如何，该算法仅使用固定数量的变量。这使得线性搜索在内存使用上很高效。

5. Binary Search Algorithm | 二分搜索算法

Binary search is a divide-and-conquer algorithm that works exclusively on sorted arrays. It repeatedly divides the search interval in half, discarding the half that cannot contain the target based on comparisons with the middle element.

二分搜索是一种分治算法，仅适用于已排序的数组。它反复将搜索区间一分为二，根据与中间元素的比较结果，丢弃不可能包含目标的那一半。

Because the search space is halved at each step, binary search dramatically reduces the number of comparisons. For a dataset of one million items, binary search needs at most about 20 comparisons, while linear search might need up to one million.

由于每一步都将搜索空间减半，二分搜索显著减少了比较次数。对于一个包含一百万条数据的数据集，二分搜索最多需要约 20 次比较，而线性搜索可能需要多达一百万次。

The crucial prerequisite is that the array must be sorted. If the data is unsorted, binary search will not work correctly, and time must be spent sorting first.

关键前提是数组必须有序。如果数据未排序，二分搜索将无法正确工作，并且需要先花费时间进行排序。

6. Binary Search Pseudocode and Walkthrough | 二分搜索伪代码与过程演示

The iterative version of binary search maintains two pointers, low and high, and calculates the midpoint. If the midpoint value matches the target, the search ends. Otherwise the appropriate half is selected.

迭代版本的二分搜索维护两个指针 low 和 high，并计算中点。如果中点值与目标匹配，搜索结束。否则选择适当的一半继续搜索。


FUNCTION binarySearch(arr, target)
    low = 0
    high = LEN(arr) - 1
    WHILE low <= high
        mid = low + (high - low) 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

Consider a sorted array [2, 5, 8, 12, 16, 23, 38, 56] and target = 23. Initially low=0, high=7, mid=3 (value 12). Since 12 < 23, low becomes mid+1 = 4. Next low=4, high=7, mid=5 (value 23), which matches, returning index 5. Without binary search, checking from the start would have taken 6 comparisons.

考虑已排序数组 [2, 5, 8, 12, 16, 23, 38, 56] 和目标值 23。初始时 low=0, high=7, mid=3（值为 12）。由于 12 < 23，low 变为 mid+1 = 4。接下来 low=4, high=7, mid=5（值为 23），匹配，返回索引 5。如果没有使用二分搜索，从开头检查将需要 6 次比较。

The midpoint calculation using low + (high - low) DIV 2 avoids integer overflow, a subtle but important implementation detail. Edexcel may accept simpler (low + high) DIV 2 in pseudocode, but demonstrating awareness of this safer method shows deeper understanding.

使用 low + (high - low) DIV 2 计算中点可以避免整数溢出，这是一个细微但重要的实现细节。Edexcel 可能在伪代码中接受更简单的 (low + high) DIV 2，但展示对这种更安全方法的认识能体现更深入的理解。

7. Analysing Binary Search Complexity | 分析二分搜索复杂度

The best case for binary search is O(1) when the middle element is the target on the first try. The average and worst cases are O(log n), as the search space halves each iteration. A logarithmic growth is extremely efficient for large inputs.

二分搜索的最佳情况是第一次尝试时中间元素即为目标，复杂度为 O(1)。平均和最坏情况均为 O(log n)，因为每一次迭代搜索空间都减半。对数增长对于大规模输入极为高效。

Case	Complexity	Example for n=1024
Best	O(1)	1 comparison
Average/Worst	O(log n)	~10 comparisons

Space complexity for the iterative version is O(1). If binary search is implemented recursively, the space complexity becomes O(log n) due to the call stack, which is still manageable but less memory-efficient.

迭代版本的空间复杂度为 O(1)。如果二分搜索采用递归实现，由于调用栈，空间复杂度变为 O(log n)，虽然仍然可控，但内存效率较低。

8. Comparison: Linear vs Binary Search | 线性搜索与二分搜索的比较

Both algorithms solve the same problem but under different constraints. Linear search does not require sorted data and works on any sequential structure, including linked lists. Binary search is much faster on large sorted arrays but demands random access and cannot be applied directly to linked lists.

两种算法解决相同的问题，但适用于不同的约束条件。线性搜索不需要数据排序，并且适用于任何顺序结构，包括链表。二分搜索在大型已排序数组上速度更快，但要求随机访问，不能直接应用于链表。

Aspect	Linear Search	Binary Search
Data requirement	Unsorted or sorted	Must be sorted
Worst-case time	O(n)	O(log n)
Best-case time	O(1)	O(1)
Space (iterative)	O(1)	O(1)
Suitable for linked lists	Yes	No (no direct indexing)
Overhead	Minimal	Sorting cost if not sorted

In exam questions you may be asked to justify the choice of a search algorithm based on the data structure and whether the overhead of sorting is worthwhile. A single search on unsorted data usually favours linear search; many searches on the same dataset favour sorting first and then using binary search.

在考试题目中，你可能需要根据数据结构以及排序的开销是否值得来论证搜索算法的选择。对未排序数据进行单次搜索通常适合用线性搜索；而在同一数据集上进行多次搜索时，则更适合先排序再使用二分搜索。

9. Choosing the Right Search Algorithm | 选择合适的搜索算法

Decision-making involves analysing the input. If the data is already sorted and the size is large, binary search is the obvious choice. If the data is unsorted and you need to search only once, linear search avoids the extra O(n log n) sorting cost.

决策涉及对输入的分析。如果数据已经排序且规模较大，二分搜索是显然的选择。如果数据未排序且只需搜索一次，线性搜索可避免额外的 O(n log n) 排序开销。

When dealing with dynamic datasets where insertions and deletions occur frequently, maintaining a sorted order can be expensive. In such scenarios linear search might be more practical because it imposes no ordering constraint.

在处理频繁插入和删除的动态数据集时，维持排序顺序可能会开销很大。在这种情况下，线性搜索可能更为实用，因为它不要求排序约束。

Additionally, if the underlying structure is a linked list, linear search is natural because each node is accessed through pointers. Binary search cannot be directly applied to linked lists without first converting the list to an array or using a skip-list structure.

此外，如果底层结构是链表，线性搜索就很自然，因为每个节点都是通过指针访问的。二分搜索无法直接应用于链表，除非先将链表转换为数组或使用跳表结构。

10. Exam Tips & Common Pitfalls | 考试技巧与常见陷阱

When writing pseudocode for binary search in an exam, always state the precondition that the array is sorted. This demonstrates algorithmic thinking. Ensure loop conditions are correct: use WHILE low <= high rather than WHILE low < high to avoid missing the final element.

在考试中为二分搜索编写伪代码时，一定要声明数组已排序的前提条件。这展示了算法思维。确保循环条件正确：使用 WHILE low <= high，而不是 WHILE low < high，以免遗漏最后一个元素。

Be careful with midpoint calculation — (low + high) DIV 2 is acceptable in Edexcel pseudocode, but if you mention overflow, use the low + (high - low) DIV 2 version for safety. Also remember to update low and high correctly (mid + 1, mid - 1) to avoid infinite loops.

在中点计算时要小心 —— Edexcel 伪代码中接受 (low + high) DIV 2，但如果你提到溢出，可以安全地使用 low + (high - low) DIV 2 版本。还要记住正确更新 low 和 high（mid + 1, mid - 1），以避免无限循环。

For linear search, do not forget the RETURN -1 after the loop to indicate that the target was not found. Many candidates lose marks by omitting this step. Also clarify whether the search returns an index or a Boolean value, as required by the question.

对于线性搜索，不要忘记在循环结束后使用 RETURN -1 来表示未找到目标。许多考生因遗漏这一步而失分。还要明确搜索返回的是索引还是布尔值，按题目要求作答。

When comparing complexities, state both time and space. Use correct Big O notation and be prepared to explain what the notation means in terms of growth rate, not exact execution time.

在比较复杂度时，要同时说明时间和空间。使用正确的大 O 表示法，并准备解释该表示法在增长率方面的含义，而不是精确的执行时间。

Finally, practice tracing both algorithms with small arrays. Exam questions frequently ask you to show each step of a linear or binary search on a given list, recording comparisons and index changes.

最后，要练习用小型数组跟踪这两种算法。考试题目经常要求你展示

Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

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

Search Algorithms: Linear and Binary Search | 搜索算法考点精讲