Algorithms, traces and correctness evidence
引入| English | 释义 | 拼音 |
|---|---|---|
| algorithm/ˈælɡərɪθəm/ | 算法 | suàn fǎ |
| trace | 追踪 | zhuī zōng |
| boundary/ˈbaʊndəri/ | 边界 | biān jiè |
| trace table/treɪs ˈteɪbl/ | 追踪表 | zhuī zōng biǎo |
| boundary test/ˈbaʊndəri test/ | 边界测试 | biān jiè cè shì |
A binary search bug hidden for years, 2006
- In 2006 Joshua Bloch of Google reported that the binary search in Java's standard library — and in many textbooks — had a bug. The line
mid = (low + high) / 2overflows whenlow + highexceeds the largest integer, which happens only for arrays of over a billion elements. The code had been in use for about nine years. - It had passed tests on small arrays. An algorithm 算法 needs evidence of correctness: traces 追踪 and tests at the boundary 边界 cases, not just typical ones.
Why did the binary search bug go unnoticed for years?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
low + high overflowed only for huge arrays.
Computational thinking
- Decomposition: split the problem. Abstraction: keep only what matters. Pattern recognition and algorithm design follow.
- State the input conditions first: binary search needs a sorted array.
Binary search requires a sorted array.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
State the input conditions first.
Linear and binary search
- Linear search checks each item: up to n comparisons, O(n).
- Binary search halves the sorted range each step: at most about log₂ n comparisons, O(log n). For 1,000,000 items, about 20.
A linear search checks every item of a 19-item list without finding the target. How many comparisons occur?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
n comparisons in the worst case.
About how many comparisons does binary search need at most for 1,000,000 sorted items?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
log₂ 1,000,000 ≈ 20.
Trace tables
- A trace table 追踪表 records each variable after each step. It shows exactly where an algorithm goes wrong.
八个元素:搜索与边界情况
比较本课八元素列表的顺序搜索与二分搜索,追踪末项匹配或目标不存在的情况;下标从零开始。
Worked example: tracing binary search
Search for 23 in A = [3, 8, 12, 17, 23, 31, 40] (indices 0–6).
low high mid A[mid] action
0 6 3 17 23 > 17 → low = 4
4 6 5 31 23 < 31 → high = 4
4 4 4 23 found at index 4
- Comparisons: 3, against up to 7 for linear search.
- Safer midpoint:
mid = low + (high - low) // 2gives the same value without overflow.
In the trace, what is mid on the first step for low = 0, high = 6?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
(0 + 6) // 2 = 3.
Boundary tests
- Test the empty array, one element, the first and last items, a missing item, and very large inputs.
- Compare each result with the expected output worked out by hand.
Which are boundary tests for a search?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Test the edges.
Passing typical tests is not proof of correctness. Bloch's bug passed every small test for years. Trace by hand and test the boundaries and extremes.
Passing typical tests proves an algorithm correct.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Test boundaries and extremes.
State an algorithm's input conditions, trace it in a table, and test boundary cases. Linear search is O(n); binary search on sorted data is O(log n). Correctness needs evidence at the edges, not just typical cases.
Write a trace table for binary search of 40 in [3, 8, 12, 17, 23, 31, 40] and list three boundary tests.
Trace and test.