Searching Algorithms: Linear Search and Binary Search | 搜索算法：线性搜索与二分搜索

📚 Searching Algorithms: Linear Search and Binary Search | 搜索算法：线性搜索与二分搜索

Searching is a fundamental operation in computer science, allowing programs to locate a specific element within a data collection. This article focuses on two core search algorithms specified by Edexcel A-Level Computer Science: linear search and binary search. Understanding their mechanisms, efficiency, and practical trade-offs is essential for both exams and real-world programming.

搜索是计算机科学中的一项基本操作，它使程序能够在数据集合中定位特定元素。本文重点介绍 Edexcel A-Level 计算机科学课程指定的两种核心搜索算法：线性搜索和二分搜索。理解它们的工作机制、效率以及实际权衡对考试和现实世界的编程都至关重要。

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

A search algorithm retrieves an item from a data structure based on a given key. The choice of algorithm affects how quickly a result can be found. In the Edexcel specification, students must be able to describe, compare, and implement linear and binary search, as well as evaluate their suitability for different scenarios.

搜索算法根据给定的键从数据结构中检索项目。算法的选择会影响找到结果的速度。在 Edexcel 大纲中，学生必须能够描述、比较和实现线性搜索与二分搜索，并评估它们在不同情境下的适用性。

2. Linear Search – The Simple Approach | 线性搜索——简单方法

Linear search, also called sequential search, inspects each element of a list one by one until the target is found or the end is reached. It does not require the data to be sorted, making it universally applicable. The algorithm uses a single loop to traverse the array, checking each element against the search key.

线性搜索，也叫顺序搜索，逐个检查列表中的每个元素，直到找到目标或到达末尾。它不要求数据有序，因此普遍适用。算法使用一个循环遍历数组，将每个元素与搜索键进行比对。

3. How Linear Search Works | 线性搜索如何工作

The procedure begins at index 0 and compares the element with the target value. If they match, the index is returned. If not, the algorithm moves to the next index. This repeats until a match is found. If the loop finishes without a match, a value such as -1 is returned to indicate failure. The algorithm is straightforward and easy to code.

过程从索引 0 开始，将元素与目标值比较。如果匹配，则返回该索引。如果不匹配，算法移至下一个索引。如此重复，直到找到匹配项。如果循环结束仍未找到，则返回 -1 之类的值表示未找到。该算法直接且易于编码。

4. Efficiency of Linear Search | 线性搜索的效率

In the worst case, the target is at the very end of the list or not present, requiring n comparisons for a list of size n. This gives linear search a time complexity of O(n). In the best case, the element is found at the first position, O(1). The average case also falls under O(n). Because it does not exploit any ordering, linear search can be slow on large datasets.

最坏情况下，目标位于列表末尾或不存在，对于大小为 n 的列表需要 n 次比较。这使线性搜索的时间复杂度为 O(n)。最好情况下，元素在第一个位置找到，O(1)。平均情况也属于 O(n)。由于不利用任何顺序，线性搜索在大数据集上可能很慢。

5. Binary Search – Divide and Conquer | 二分搜索——分治法

Binary search dramatically reduces the number of comparisons by repeatedly dividing the search interval in half. It is a divide-and-conquer algorithm that requires the list to be sorted beforehand. The algorithm compares the target with the middle element; depending on the result, it discards the half that cannot contain the target, continuing on the remaining half.

二分搜索通过反复将搜索区间减半，显著减少了比较次数。它是一种分治算法，需要列表事先排序。算法将目标与中间元素比较；根据结果，丢弃不可能包含目标的那一半，在剩下的一半上继续搜索。

6. Preconditions for Binary Search | 二分搜索的前提条件

The array or list must be sorted in ascending or descending order. If the data is unsorted, binary search will not work correctly and may miss the target or loop indefinitely. Sorting itself can be costly, so binary search is most effective when multiple searches are performed on the same sorted data structure.

数组或列表必须按升序或降序排列。如果数据未排序，二分搜索将无法正确工作，可能找不到目标或无限循环。排序本身可能代价高昂，因此二分搜索最适用于对同一已排序数据结构执行多次搜索的情况。

7. Step-by-Step Binary Search | 二分搜索逐步解析

Two pointers, low and high, mark the current search boundaries. Initially, low = 0 and high = len(list)-1. While low <= high, compute mid = (low + high) // 2. If the middle element equals the target, return mid. If the target is smaller, set high = mid - 1; if larger, set low = mid + 1. If low surpasses high, the item is not found and the procedure returns an error value.

用两个指针 low 和 high 标记当前搜索边界。初始时 low = 0, high = len(list)-1。当 low <= high，计算 mid = (low + high) // 2。如果中间元素等于目标，返回 mid。如果目标更小，则设 high = mid - 1；如果更大，则设 low = mid + 1。一旦 low 超过 high，表示未找到，程序返回错误值。

8. Efficiency of Binary Search | 二分搜索的效率

Each comparison halves the search space, so the maximum number of steps is about log₂(n). Thus, binary search has a time complexity of O(log n) in the worst and average cases. The best case remains O(1) if the middle element happens to be the target. This logarithmic efficiency makes binary search vastly superior to linear search on large sorted datasets.

每次比较将搜索空间减半，因此最大步数大约为 log₂(n)。这样，二分搜索在最坏和平均情况下的时间复杂度为 O(log n)。最好情况如果中间元素恰好是目标，仍为 O(1)。这种对数级效率使得二分搜索在大型有序数据集上远优于线性搜索。

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

Linear search works on any list, is simple to implement, and performs well on small or nearly full arrays where the target appears early. Binary search requires sorted data and more complex logic, but it excels with large n. A comparison of their worst-case complexities shows that for n = 1,000,000, linear search may take 1 million checks, while binary search needs at most 20. The trade-off lies in the sorting overhead.

线性搜索适用于任何列表，实现简单，在小型数组或目标出现较早时表现良好。二分搜索需要排序数据和更复杂的逻辑，但在 n 很大时表现优异。最坏情况复杂度的对比表明，当 n = 1,000,000 时，线性搜索可能需要 100 万次检查，而二分搜索最多只需 20 次。权衡在于排序的开销。

10. Implementing in Pseudocode and Python | 伪代码与Python实现

Edexcel expects students to write and trace both algorithms. Below are concise examples. For linear search in Python:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

For binary search:

def binary_search(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Edexcel 期望学生能够编写和追踪这两种算法。下面是简洁的示例。Python 线性搜索：

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

二分搜索：

def binary_search(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

11. Searching in Real-world Applications | 实际应用中的搜索

Linear search is often used in small unsorted lists, such as finding a name in a short contact list, or when scanning streaming data where sorting isn't possible. Binary search underpins operations in database indexing, dictionary lookups, and filesystem searches on sorted keys. Understanding both helps programmers design appropriate data structures.

线性搜索常用在小的无序列表中，比如在简短的联系人列表中查找姓名，或者在无法排序的流式数据中扫描。二分搜索则支撑着数据库索引、字典查找以及基于排序键的文件系统搜索等操作。理解两者有助于程序员设计合适的数据结构。

12. Exam Tips and Common Pitfalls | 考试技巧与常见误区

When describing binary search, always emphasise that the list must be sorted. Many candidates lose marks for forgetting this crucial detail. Trace tables are common in exams; practise tracking low, mid, and high values step by step. Remember that binary search uses integer division for the midpoint. For linear search, be clear that the algorithm stops when found, which is essential for efficiency calculations.

在描述二分搜索时，务必强调列表必须有序。许多考生因遗漏这一关键细节而失分。考试中常出现跟踪表；请逐步练习记录 low、mid 和 high 的值。记住二分搜索的中点使用整数除法。对于线性搜索，要明确算法找到目标后即停止，这对效率计算至关重要。

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

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

Searching Algorithms: Linear Search and Binary Search | 搜索算法：线性搜索与二分搜索