Binary Search
Introduced| English | Meaning |
|---|---|
| sorted/ˈsɔːtɪd/ | Arranged according to a specified ordering, such as increasing numerical value. |
| Binary search/ˈbaɪnəri sɜːtʃ/ | A fast way to locate a target value in a sorted list. |
| target/ˈtɑːɡɪt/ | target |
| middle/ˈmɪdl/ | middle |
| halves/hɑːvz/ | halves |
| comparison/kəmˈpærɪsn/ | Examining two or more items to identify similarities, differences or their relative order. |
| linear search/ˈlɪnɪə sɜːtʃ/ | Checking items in sequence until the required item is found or the list ends. |
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:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
A larger target must be in the right (higher) half.
Each comparison in binary search ______ the remaining part of the list.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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)
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Middle 11 → right; middle 17 → left; middle 14 → found: 3 comparisons.
On a large sorted list, linear search needs fewer comparisons than binary search.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.