| English | 意味 |
|---|---|
| sorted/ˈsɔːtɪd/ | ソート済み |
| Binary search/ˈbaɪnəri sɜːtʃ/ | 二分探索 |
| target/ˈtɑːɡɪt/ | ターゲット |
| middle/ˈmɪdl/ | 中央 |
| halves/hɑːvz/ | 半分 |
| comparison/kəmˈpærɪsn/ | 比較 |
| linear search/ˈlɪnɪə sɜːtʃ/ | 線形探索 |
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 can only be used on data that is:
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
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.
Binary search halves 减半 the range at each step (the list must be sorted)
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:
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
A larger target must be in the right (higher) half.
Each comparison in binary search ______ the remaining part of the list.
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
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)
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
Because 2^10 = 1024 ≥ 1000, about 10 halvings suffice.
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.
Binary search finds 14 in [2,5,8,11,14,17,20] in how many comparisons?
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
Middle 11 → right; middle 17 → left; middle 14 → found: 3 comparisons.
On a large sorted list, linear search needs fewer comparisons than binary search.
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
False. Binary search halves the list at each step, so it needs far fewer comparisons than checking every item in turn.
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.
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.