📚 Search Algorithms for IGCSE AQA Computer Science | IGCSE AQA 计算机：搜索算法考点精讲
Search algorithms are essential techniques in computer science that allow us to locate specific data items within a larger collection. Whether you are searching for a contact on your phone or a product in an online store, an efficient search algorithm can save time and computing resources. In the IGCSE AQA Computer Science syllabus, you are expected to understand, describe, and compare two core search methods: linear search and binary search.
搜索算法是计算机科学中必不可少的技术，它使我们能够在更大的数据集合中定位特定的数据项。无论你是在手机上搜索联系人，还是在网店中查找商品，高效的搜索算法都能节省时间和计算资源。在 IGCSE AQA 计算机科学大纲中，你需要理解、描述并比较两种核心搜索方法：线性搜索和二分搜索。
1. What are Search Algorithms? | 什么是搜索算法？
A search algorithm is a step-by-step procedure used to retrieve information stored within some data structure. The goal is to find whether a particular item, called the target or key, exists in the dataset and, if so, its position.
搜索算法是一种逐步操作的过程，用于检索存储在某些数据结构中的信息。其目标是找出特定的项（称为目标或键）是否存在于数据集中，如果存在，则找出它的位置。
Search algorithms are measured by their efficiency, which often depends on the size of the data and whether it is sorted. In this unit, we focus on two fundamental approaches: sequential (linear) search and binary search.
搜索算法的效率是衡量其性能的关键，通常取决于数据的大小以及数据是否有序。在本单元中，我们重点介绍两种基本方法：顺序（线性）搜索和二分搜索。
2. Linear Search (Sequential Search) | 线性搜索（顺序搜索）
Linear search is the simplest searching technique. It checks every element of a list one by one, starting from the beginning, until a match is found or the whole list has been examined.
线性搜索是最简单的搜索技术。它从列表的开头开始，逐个检查每一个元素，直到找到匹配项或检查完整个列表。
- Start at index 0 — 从索引0开始。
- Compare the current element with the target value — 将当前元素与目标值比较。
- If they match, return the index — 如果匹配，返回索引。
- If not, move to the next element — 如果不匹配，移动到下一个元素。
- If the end of the list is reached without a match, return -1 or a message indicating the target is not present — 如果到达列表末尾仍未找到匹配，返回-1或提示目标不存在。
Linear search works on both unsorted and sorted lists, making it very flexible. However, it can be slow for large datasets because, in the worst case, it must inspect every element.
线性搜索既适用于无序列表，也适用于有序列表，因此非常灵活。然而，对于大型数据集，它可能很慢，因为在最坏的情况下，它必须检查每一个元素。
3. Binary Search | 二分搜索
Binary search is a much more efficient algorithm but has a critical requirement: the list must be sorted beforehand. It works by repeatedly dividing the search interval in half.
二分搜索是一种高效得多的算法，但有一个关键要求：列表必须事先排序。它通过反复将搜索区间分成两半来工作。
- Find the middle element of the sorted list — 找到有序列表的中间元素。
- If the middle element equals the target, the search is complete — 如果中间元素等于目标，搜索结束。
- If the target is smaller than the middle element, repeat the search on the left half — 如果目标小于中间元素，在左半部分重复搜索。
- If the target is larger, repeat on the right half — 如果目标更大，在右半部分重复搜索。
- Continue until the target is found or the subarray has no elements — 继续直到找到目标或子数组没有元素为止。
Binary search dramatically reduces the number of comparisons needed. For example, in a list of 1000 sorted items, binary search finds the target in at most about 10 steps, whereas linear search might need up to 1000.
二分搜索大幅减少了所需的比较次数。例如，在一个包含1000个有序项的列表中，二分搜索最多只需大约10步就能找到目标，而线性搜索可能需要多达1000步。
4. Pseudocode of Linear Search | 线性搜索的伪代码
Understanding pseudocode is vital for the AQA exam. Below is a standard representation of linear search:
FOR index ← 0 TO LENGTH(list) - 1
IF list[index] = target THEN
OUTPUT index
STOP
ENDIF
NEXT index
OUTPUT -1
理解伪代码对AQA考试至关重要。以下是线性搜索的标准表示：
循环 索引 从 0 到 列表长度 - 1
如果 列表[索引] = 目标Published by TutorHao | IGCSE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导