← DSA I

Search strategy laboratory

Search Lab

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) {
2 int lo = 0, hi = n - 1;
3 while (lo <= hi) {
4 int mid = lo + (hi - lo) / 2;
5 if (a[mid] == t) return mid;
6 if (a[mid] < t) lo = mid + 1; else hi = mid - 1;
7 }
8 return -1;
9}
target23
lo0
hi7
mid—
extra memory 2 bounds
0 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

worst
fixed 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.

  1. Each midpoint comparison discards half the remaining range: 8 → 4 → …
  2. At most ⌊log₂ 8⌋ + 1 = 4 midpoints are ever inspected.
  3. 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.

1 / 8