Searching Algorithms · 查找算法
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| Searching/ˈsɜːtʃɪŋ/ | 查找 | chá zhǎo |
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
| binary search/ˈbaɪnəri sɜːtʃ/ | 二分查找 | èr fēn chá zhǎo |
| sorted/ˈsɔːtɪd/ | 已排序 | yǐ pái xù |
Finding a value
- Searching 查找 means locating a target value in a collection.
- Two standard algorithms: linear search 线性查找 and binary search 二分查找.
- Both return the index where the target sits — or a "not found" signal (often
-1). - Which one you may use depends on whether the data is sorted.
查找一个值
- 查找指在一个集合中定位目标值。
- 两个标准算法：线性查找和二分查找。
- 两者都返回目标所在的下标——或一个“未找到”信号（常为
-1）。 - 你能用哪一个，取决于数据是否已排序。
Linear search
- Check each element from the start, one by one, until you find the target.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Works on any array — sorted or not.
- Worst case: it looks at every element (
nchecks).
线性查找
- 从头开始逐个检查每个元素，直到找到目标。
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- 对任何数组都有效——排序与否都行。
- 最坏情况：它检查每个元素（
n次检查）。
Binary search
- Needs a sorted 已排序 array. Look at the middle element each time.
- If the middle is the target, done. If the target is smaller, search the left half; if larger, the right half.
- Each step halves the range that's left to search.
- Far faster on large sorted arrays — about
log₂ nchecks, notn.
二分查找
- 需要一个已排序的数组。每次看中间的元素。
- 若中间就是目标，完成。若目标更小，查找左半；若更大，查找右半。
- 每一步把剩下要查的范围减半。
- 在大的已排序数组上快得多——约
log₂ n次检查，而非n。
Why binary search is fast
- Linear search of a million items: up to a million checks.
- Binary search of a million sorted items: about 20 checks.
- The catch: the array must already be sorted.
- Halving repeatedly is the big idea behind
O(log n).
二分查找为何快
- 对一百万个元素做线性查找：多达一百万次检查。
- 对一百万个已排序元素做二分查找：约 20 次检查。
- 代价：数组必须已经排好序。
- 反复减半是
O(log n)背后的大主意。
Binary search only works on a SORTED array — running it on unsorted data gives wrong answers. It also compares to the middle and throws away half the range each step; a linear search compares from the start and drops just one element. If you're not sure the data is sorted, you must use linear search (or sort first).
二分查找只对已排序数组有效——在未排序数据上运行会给出错误答案。它还是与中间比较、每步丢弃一半范围；线性查找从开头比较、每次只丢一个元素。若你不确定数据是否已排序，就必须用线性查找（或先排序）。
Binary search for 7 in [1, 3, 5, 7, 9]:
- Middle is
5(index 2). 7 > 5, so search the right half. - Right half is
[7, 9]; middle is7. Found at index 3. - Two checks instead of four — the range halved each time.
在 [1, 3, 5, 7, 9] 中二分查找 7：
- 中间是
5（下标 2）。7 > 5，所以查找右半。 - 右半是
[7, 9]；中间是7。在下标 3 找到。 - 两次检查而非四次——范围每次减半。
Linear search checks elements from the start (works on any array, up to n checks). Binary search needs a sorted array, compares to the middle, and halves the search range each step (about log₂ n checks). Both return the index found, or a "not found" signal like -1.
线性查找从头检查元素（对任何数组有效，最多 n 次检查）。二分查找需要一个已排序数组，与中间比较，每步把查找范围减半（约 log₂ n 次检查）。两者都返回找到的下标，或一个像 -1 的“未找到”信号。
Linear vs binary search · 线性 vs 二分查找
Binary search halves the sorted range each step. · 二分查找每步把已排序范围减半。
A linear search... · 线性查找……
Linear = start to end; works on any array. · 线性 = 从头到尾；对任何数组都行。
Binary search requires the array to be... · 二分查找要求数组是……
Binary search only works on sorted data. · 二分查找只对已排序数据有效。
Each step of binary search... · 二分查找的每一步……
It compares to the middle and keeps one half. · 它与中间比较并保留一半。
Binary search in [1,3,5,7,9] for 7: how many comparisons (middle each time)? · 在 [1,3,5,7,9] 中二分查找 7：多少次比较（每次取中间）？
Compare to 5, then to 7 — two comparisons. · 先比 5，再比 7——两次比较。
Binary search gives correct results on an UNSORTED array. · 二分查找在未排序数组上给出正确结果。
It relies on order; unsorted data breaks it. · 它依赖顺序；未排序数据会破坏它。
Match each search to its property. · 把每种查找与其性质配对。
Linear is general but slower; binary is fast but needs order. · 线性通用但较慢；二分快但需要顺序。