Binary Search
Introduced| English |
|---|
| sorted/ˈsɔːtɪd/ |
| Binary search/ˈbaɪnəri sɜːtʃ/ |
| target/ˈtɑːɡɪt/ |
| middle/ˈmɪdl/ |
| comparison/kəmˈpærɪsn/ |
| halves/hɑːvz/ |
| 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:
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.
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)
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?
Middle 11 → right; middle 17 → left; middle 14 → found: 3 comparisons.
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.
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.