Binary Search | 二分查找

📚 Binary Search | 二分查找

Binary search is a fundamental searching algorithm in A-Level Computer Science that finds the position of a target value within a sorted list. It repeatedly halves the search space, which makes it far more efficient than linear search for large data sets.

二分查找是 A-Level 计算机科学中的一种基础搜索算法，用于在有序列表中查找目标值的位置。它不断将搜索范围减半，因此在大型数据集上比线性查找高效得多。

1. What is Binary Search? | 什么是二分查找？

Binary search is an algorithm that locates a target item in a sorted array or list by comparing the target with the middle element. If the middle element matches the target, the search stops. Otherwise the algorithm decides whether to continue searching in the left half or the right half.

二分查找是一种通过在有序数组或列表中将目标值与中间元素进行比较来定位目标项的算法。如果中间元素与目标值匹配，则搜索停止；否则算法决定继续在左半部分还是右半部分中搜索。

Unlike linear search, binary search does not examine every element from the beginning. It exploits the sorted order to discard half of the remaining elements after each comparison.

与线性查找不同，二分查找不会从头开始检查每个元素。它利用有序性，在每次比较后舍弃剩余元素的一半。

2. Core Idea: Divide and Conquer | 核心思想：分而治之

The algorithm follows a divide-and-conquer strategy. The problem of searching the whole list is reduced to searching a smaller sub-list. Each step divides the current search interval into two halves.

该算法采用分而治之的策略。搜索整个列表的问题被简化为搜索一个较小的子列表。每一步都将当前搜索区间分成两半。

Because the list is sorted, the algorithm can determine which half could contain the target by checking the middle value. If the target is greater than the middle value, the left half can be ignored; if it is smaller, the right half can be ignored.

由于列表是有序的，算法可以通过检查中间值来确定哪一半可能包含目标值。如果目标值大于中间值，则可以忽略左半部分；如果目标值小于中间值，则可以忽略右半部分。

This halving behaviour is why the number of comparisons grows much more slowly than the number of items.

这种减半行为正是比较次数增长速度远慢于元素数量的原因。

3. Preconditions: Sorted Data | 前提条件：有序数据

Binary search only works correctly on sorted data. If the list is not sorted, the assumption that all values left of the middle are smaller and all values right are larger is false.

二分查找只有在数据有序时才能正确工作。如果列表未排序，那么 ‘中间值左边都更小、右边都更大’ 的假设就不成立。

For Edexcel A-Level questions, you

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

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