Algorithms, traces and correctness evidence
Introduced| English | Meaning |
|---|---|
| algorithm/ˈælɡərɪθəm/ | A finite sequence of precise steps for solving a problem or carrying out a task. |
| 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/ | A test using values at, just inside or just outside the limits of an allowed input range. |
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?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
n comparisons in the worst case.
About how many comparisons does binary search need at most for 1,000,000 sorted items?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
(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?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.