Binary Search
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| sorted/ˈsɔːtɪd/ | đã sắp xếp |
| Binary search/ˈbaɪnəri sɜːtʃ/ | tìm kiếm nhị phân |
| target/ˈtɑːɡɪt/ | mục tiêu |
| middle/ˈmɪdl/ | giữa |
| halves/hɑːvz/ | phân đôi |
| comparison/kəmˈpærɪsn/ | so sánh |
| linear search/ˈlɪnɪə sɜːtʃ/ | tìm kiếm tuyến tính |
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:
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
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:
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
A larger target must be in the right (higher) half.
Each comparison in binary search ______ the remaining part of the list.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
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)
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
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?
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Middle 11 → right; middle 17 → left; middle 14 → found: 3 comparisons.
On a large sorted list, linear search needs fewer comparisons than binary search.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
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.