📚 Binary Search | 二分查找
Searching is a core operation in computer science, and understanding efficient algorithms is essential for any A‑Level student. Binary search stands out as a classic divide‑and‑conquer technique that dramatically reduces the number of comparisons needed to locate an item. In the Edexcel specification, you are expected to know how binary search works, when it can be applied, its time complexity, and how it compares with linear search.
搜索是计算机科学中的核心操作，理解高效算法对每一位 A‑Level 学生来说都至关重要。二分查找作为一种经典的分治算法，能够大幅减少查找目标所需的比较次数，因此格外突出。在 Edexcel 考试大纲中，你需要掌握二分查找的工作原理、适用条件、时间复杂度以及它与线性查找的对比。
1. Searching Algorithms Overview | 搜索算法概览
Search algorithms retrieve information stored within a data structure. The simplest method is a linear search, which checks every element sequentially. While easy to implement, it becomes inefficient on large datasets. Binary search offers a much faster alternative when the data is sorted, exploiting the order to eliminate half of the remaining elements at each step.
搜索算法用于查找数据结构中存储的信息。最简单的方法是线性查找，它按顺序逐个检查每一个元素。虽然实现简单，但在面对大型数据集时效率很低。当数据处于有序状态时，二分查找提供了一种快得多的替代方案，它利用数据的有序性，每一步都能排除掉剩下的一半元素。
2. What is Binary Search? | 什么是二分查找？
Binary search is an algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. It follows a "divide and conquer" strategy: compare the target with the middle element, discard the half where the target cannot lie, and repeat the process on the remaining half until the value is found or the interval is empty.
二分查找是一种用于在有序数组中查找目标值位置的算法，通过反复将搜索区间一分为二来逐步逼近。它遵循“分而治之”的策略：将目标值与中间元素比较，丢弃不可能包含目标的那一半，然后在剩下的一半上重复该过程，直到找到目标或区间为空。
3. Prerequisite – Sorted Data | 前提条件——有序数据
Binary search can only be applied to a collection that is sorted in ascending or descending order. If the data is unsorted, the algorithm will produce incorrect results. The sorting order must be consistent; for an ascending array, after comparing the target with the middle value, you know whether to search the left or the right sub‑array based on whether the target is smaller or larger.
二分查找只能应用于按升序或降序排列的数据集合。如果数据是无序的，算法将产生错误的结果。排序的顺序必须一致；对于升序排列的数组，将目标值与中间值比较后，就可以根据目标值是更小还是更大来确定是继续搜索左子数组还是右子数组。
4. How Binary Search Works – Step‑by‑Step | 二分查找的工作步骤
ay A of n elements and a target value T. Set two pointers, low and high, initially 0 and n‑ ing low = mid + 1. If A[mid] > T, discard the right half by setting high = mid - 1. Continue until low > high, meaning the target is not in the array.
假设有一个包含 n 个元素的有序数组 A 和一个目标值 T。设置两个指针 low 和 high，初始值分别为 0 和 n‑1。然后重复以下步骤：计算 mid = (low + high) 整除 2。如果 A[mid] 等于 T，则查找成功。如果 A[mid] < T，则令 low = mid + 1，丢弃左半部分。如果 A[mid] > T，则令 high = mid - 1，丢弃右半部分。持续这一过程，直到 low > high，此时意味着目标值不在数组中。
[7] = 45. 23 < 45, so high becomes 6. Next mid = (5+6)//2 = 5, A[5] = 23. Found at index 5.
例如，在 [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] 中查找 23。第一次 mid = (0+9)//2 = 4，A[4] = 16。由于 23 > 16，low 变为 5。接着 mid = (5+9)//2 = 7，A[7] = 45。23 < 45，因此 high 变为 6。然后 mid = (5+6)//2 = 5，A[5] = 23。在索引 5 处找到目标。
5. Pseudocode Representation | 伪代码表示
An iterative pseudocode for binary search can be written as:
二分查找的迭代伪代码可以写成：
FUNCTION binarySearch(arr, target)
low ← 0
high ← LENGTH(arr) - 1
WHILE low ≤ high
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
This pseudocode highlights the core logic and can be implemented in Python, Java or any other language. The integer division (DIV) ensures that mid is a valid index. The loop terminates when the sub‑array size becomes zero.
这段伪代码突出了核心逻辑，并可以用 Python、Java 或任何其他语言实现。整数除法 (DIV) 确保 mid 是合法的索引。当子数组长度变为零时，循环终止。
6. Iterative vs. Recursive Implementation | 迭代与递归实现
Binary search can be implemented iteratively as shown above or recursively. A recursive version calls itself on a smaller sub‑array. For example, the base cases are: if low > high, return -1; if arr[mid] equals target, return mid. Otherwise, if target is smaller, recursively search the left half; if larger, search the right half. Recursion can be elegant but may cause stack overflow for large arrays, whereas the iterative version uses constant extra space O(1).
二分查找可以像上面那样迭代实现，也可以递归实现。递归版本在较小的子数组上调用自身。例如，基准条件是：如果 low > high，返回 -1；如果 arr[mid] 等于目标值，返回 mid。否则，如果目标值较小，递归搜索左半部分；如果较大，搜索右半部分。递归写法优雅，但对于极大的数组可能导致栈溢出，而迭代版本仅使用 O(1) 的额外空间。
7. Time Complexity Analysis | 时间复杂度分析
The efficiency of binary search is measured by its time complexity. In the worst case, the interval is halved repeatedly until it contains one element. The number of comparisons is roughly log₂ n, where n is the number of elements. Hence the worst‑case time complexity is O(log₂ n). The best case occurs when the middle element is the target immediately, giving O(1).
二分查找的效率由时间复杂度衡量。在最坏情况下，搜索区间被反复折半，直至只剩一个元素。比较次数大约为 log₂ n，其中 n 是元素个数。因此最坏情况时间复杂度为 O(log₂ n)。最好情况是中间元素正好就是目标值，时间复杂度为 O(1)。
Space complexity for the iterative version is O(1), since only a few variables are used. The recursive version has O(log₂ n) space complexity due to the call stack. When comparing to linear search with O(n) time, binary search is exponentially faster for large n.
迭代版本的空间复杂度为 O(1)，因为只使用了少量变量。递归版本由于调用栈的存在，空间复杂度为 O(log₂ n)。与时间复杂度为 O(n) 的线性查找相比，当 n 很大时，二分查找的速度呈指数级提升。
8. Comparing Binary Search and Linear Search | 二分查找与线性查找的比较
The table below summarises the key differences between binary search and linear search. Remember that binary search requires sorted data, but its logarithmic time makes it far superior for large datasets.
下表总结了二分查找和线性查找的主要区别。请记住，二分查找要求数据有序，但其对数级的时间复杂度使其在大数据集上具有压倒性优势。
| Aspect | Binary Search | Linear Search |
| Data requirement | Must be sorted | Works on unsorted data |
| Worst-case time | O(log₂ n) | O(n) |
| Best-case time | O(1) | O(1) |
| Space (iterative) | O(1) | O(1) |
| Implementation | Slightly more complex | Very simple |
| Suitability | Large, static sorted datasets | Small or frequently changing lists |
9. Advantages and Limitations | 优点与局限性
Binary search is extremely fast on large sorted collections. It reduces the search space exponentially, making it suitable for databases, dictionaries, and any application where quick look‑up is critical. The algorithm is relatively easy to implement and test.
二分查找在大型有序集合上速度极快。它呈指数级地缩小搜索空间，因此非常适合用于数据库、字典以及任何对快速查找有严格要求的应用。该算法实现和测试也相对容易。
However, the data must be sorted beforehand, which itself takes O(n log₂ n) time. If the dataset changes frequently (insertions and deletions), maintaining the sorted order can be expensive. Binary search also requires random access to elements, so it cannot be applied efficiently to linked lists.
然而，数据必须预先排序，而排序本身需要 O(n log₂ n) 的时间。如果数据集频繁变动（插入和删除），维护有序状态的代价可能很高。二分查找还需要能够随机访问元素，因此无法高效地应用于链表结构。
10. Real‑world Applications | 实际应用场景
Binary search is used in many real‑world systems. It underpins the functionality of search features in sorted arrays, library catalogues, and look‑up tables in compilers. Debugging tools often use a form of binary search to isolate faulty commits (git bisect). In competitive programming, it helps solve problems on monotonic functions. Understanding binary search also builds a foundation for more advanced data structures such as binary search trees.
二分查找在许多实际系统中都有应用。它支撑着有序数组中的搜索功能、图书馆目录以及编译器中的查找表。调试工具常借助类似二分查找的方法定位引入了缺陷的提交（例如 git bisect）。在算法竞赛中，它有助于解决单调函数相关的问题。理解二分查找还为学习二叉搜索树等更高级的数据结构奠定了基础。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图