Algorithms, traces and correctness evidence
Introduit| English | Sens |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algorithm : algorithme |
| trace | to follow an algorithm step by step, recording the values of its variables |
| boundary/ˈbaʊndəri/ | A line, surface or limit that separates regions or marks the extent of an area or set. |
| trace table/treɪs ˈteɪbl/ | A table recording variable values, conditions or outputs while an algorithm is followed step by step. |
| boundary test/ˈbaʊndəri test/ | boundary test : test aux limites |
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?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
n comparisons in the worst case.
About how many comparisons does binary search need at most for 1,000,000 sorted items?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
log₂ 1,000,000 ≈ 20.
Trace tables
- A trace table 追踪表 records each variable after each step. It shows exactly where an algorithm goes wrong.
Search probes and boundary cases
Compare linear search with binary search on sorted data. Trace a match or an absent target; indices start at zero.
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?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
(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?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.