0/5 traced
Binary Search (iterative)
Halve a sorted range with a loop until the target or an empty range remains.
worst case O(log n) time O(1) space
1int bsearch_it(const int* a, int n, int t) {2int lo = 0, hi = n - 1;3while (lo <= hi) {4int mid = lo + (hi - lo) / 2;5if (a[mid] == t) return mid;6if (a[mid] < t) lo = mid + 1; else hi = mid - 1;7}8return -1;9}
target
23lo
0hi
7mid
—extra memory
2 bounds0 2
1 5
2 8
3 12
4 16
5 23
6 38
7 56
Compared Discarded unseenMidpoint
Exact work through this line 2 +2 on this line
O(log n) time O(1) auxiliary space 0 peak reported values
0comparisons
0reads
2writes
0pointer reads
0pointer writes
0swaps
0allocations
0deallocations
0node visits
0iterations
0calls
0returns
Variables before line
inull
resultnull
nodes
Variables after line
inull
resultnull
nodes
Reads, writes, and state changes on this line
left.value null → 0 highlight
right.value null → 7 highlight
Why this bound?
O(log n) time · O(1) space
worstfixed readfixed writeInput may grow; this fixed-width work does not → 1
Auxiliary memory model
cursortemporarycounter
A bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.
- Each midpoint comparison discards half the remaining range: 8 → 4 → …
- At most ⌊log₂ 8⌋ + 1 = 4 midpoints are ever inspected.
- Halving until one element remains is the definition of O(log n); two bounds are O(1) space.
Assumptions behind this claim
- The array is sorted ascending; binary search is meaningless without it.
- Values are distinct so every search has a single well-defined answer.
- Each displayed comparison, read, hash, or pointer move is one counted primitive.
- Trace construction and visualization bookkeeping are excluded from the algorithm count.
Step 1 of 8 · init-range Initialize lo = 0, hi = 7
Two integers bound the search range; they are the only extra memory the loop ever uses.
About this implementation
The scoreboard counts exact comparisons for the current target across all five strategies on the same data. Linear scans up to n; binary halves a sorted range (O(log n)); a balanced BST is O(log n) but a skewed one is O(n); hashing computes the bucket directly for expected O(1). The BST is built in the order you type, so insertion order decides its shape.