Binary Search · 二分查找
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| sorted/ˈsɔːtɪd/ | 已排序 | yǐ pái xù |
| Binary search/ˈbaɪnəri sɜːtʃ/ | 二分查找 | èr fēn chá zhǎo |
| target/ˈtɑːɡɪt/ | 目标 | mù biāo |
| middle/ˈmɪdl/ | 中间 | zhōng jiān |
| comparison/kəmˈpærɪsn/ | 比较 | bǐ jiào |
| halves/hɑːvz/ | 减半 | jiǎn bàn |
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
Finding fast in a sorted list
- Binary search 二分查找 is a fast way to locate a target 目标 value in a sorted 已排序 list.
- "Sorted" means the values are in order — smallest to largest, say.
- It is far faster than checking every item.
- But it has one strict requirement.
Binary search needs sorted data. On an unsorted list it can jump past the target and miss it. Always sort first — or use a different search.
在已排序列表中快速查找
- 二分查找(binary search)是在已排序(sorted)列表中定位一个目标(target)值的快速方法。
- "已排序"意味着值是有序的——比如从小到大。
- 它比检查每一项快得多。
- 但它有一个严格的要求。
二分查找需要已排序的数据。 在未排序的列表上,它可能跳过目标而错过它。总是先排序——或用另一种查找。
Binary search can only be used on data that is: · 二分查找只能用在什么样的数据上:
On unsorted data it can miss the target. · 在未排序数据上它可能错过目标。
Check the middle, then halve
- The idea is simple: check the middle 中间 element. Then:
- if the middle equals the target, you found it;
- if the target is smaller, search only the left half;
- if the target is larger, search only the right half.
检查中间,然后减半
- 想法很简单:检查中间(middle)元素。然后:
- 如果中间等于目标,你找到了;
- 如果目标更小,只搜索左半;
- 如果目标更大,只搜索右半。
Linear vs binary search · 线性查找与二分查找
binary halves the range each step · 二分每步把范围减半
Linear search checks every item; binary search halves a sorted list each comparison, so it needs far fewer steps. · 线性查找检查每个项;二分查找每次比较把已排序列表减半,所以需要少得多的步骤。
If the target is larger than the middle element, binary search next looks in the: · 如果目标大于中间元素,二分查找接下来看:
A larger target must be in the right (higher) half. · 更大的目标必在右(更高的)半。
Each comparison in binary search ______ the remaining part of the list. · 二分查找中每次比较把列表剩余部分______。
Halving each step is why it is so fast. · 每步减半是它这么快的原因。
About how many binary-search checks are needed for a sorted list of 1000 items? (2^10 = 1024) · 一个 1000 项的已排序列表大约需要多少次二分查找?(2^10 = 1024)
Because 2^10 = 1024 ≥ 1000, about 10 halvings suffice. · 因为 2^10 = 1024 ≥ 1000,约 10 次减半就够。
Why it is so fast
- Each comparison 比较 halves 减半 the remaining part of the list.
- For 1000 items, a linear search may need up to 1000 checks.
- Binary search needs at most about 10, because $2^{10} = 1024$.
- The larger the list, the bigger the advantage.
为什么它这么快
- 每次比较(comparison)把列表剩余部分减半(halves)。
- 对 1000 项,线性搜索可能需要多达 1000 次检查。
- 二分查找最多需要约 10 次,因为 $2^{10} = 1024$。
- 列表越大,优势越大。
Binary search finds 14 in [2,5,8,11,14,17,20] in how many comparisons? · 二分查找在 [2,5,8,11,14,17,20] 中找到 14 用了多少次比较?
Middle 11 → right; middle 17 → left; middle 14 → found: 3 comparisons. · 中间 11 → 右;中间 17 → 左;中间 14 → 找到:3 次比较。
On a large sorted list, binary search needs far fewer comparisons than linear search. · 在一个大的已排序列表上,二分查找需要的比较远少于线性查找。
Halving beats checking every item one by one. · 减半胜过一个一个地检查每项。
Versus linear search
- A linear search 线性查找 checks every element one by one.
- Binary search beats it on large sorted lists by halving each step.
Search [2, 5, 8, 11, 14, 17, 20] for 14. Middle is 11; 14 > 11 → search the right half [14, 17, 20]. Middle is 17; 14 < 17 → search [14]. Middle is 14 — found in just 3 comparisons. A linear search would have taken 5.
对比线性搜索
- 一个线性查找(linear search)一个一个地检查每个元素。
- 二分查找在大的已排序列表上通过每步减半胜过它。
在 [2, 5, 8, 11, 14, 17, 20] 中搜索 14。 中间是 11;14 > 11 → 搜索右半 [14, 17, 20]。中间是 17;14 < 17 → 搜索 [14]。中间是 14——只用 3 次比较找到。线性搜索本会用 5 次。
Binary search finds a target in a sorted list by checking the middle and keeping only the half that could contain it. Each comparison halves the range, so 1000 items need ~10 checks — far fewer than a linear search's 1000. It works only on sorted data.
二分查找通过检查中间并只保留可能含有它的那一半,在已排序列表中找到目标。每次比较****减半范围,所以 1000 项需要约 10 次检查——远少于线性查找的 1000 次。它只在已排序数据上有效。