Binary Search / Sorted-Array Step Visualizer mechanism

Model scope

The core algorithm is valid only after specifying integer midpoint rounding, bounds, comparison-count semantics, duplicate handling, and the baseline convention. The supplied logarithmic expression is at best a rough educational estimate and is not an exact per-search step count; for the standard inclusive implementation, a common worst-case upper bound is ceil(log2(n+1)) midpoint inspections, with the n=8 vector demonstrating why ceil(log2(n)) is insufficient. The honest label should state that inputs must be sorted and that the displayed logarithmic count is an estimate or worst-case bound, not the actual trace length.

• The midpoint formula mid=(lo+hi)/2 can produce a non-integer index; standard binary search requires integer rounding, typically floor(lo+(hi-lo)/2).
• step count ≈ ceil(log2(n)) is not the exact comparison count for a particular target and is not always a valid worst-case bound under the usual inclusive [lo, hi] search. For example, n=8 can require 4 midpoint inspections, while ceil(log2(8))=3.
• The specification does not define whether comparisons means midpoint inspections or primitive comparisons such as equality plus ordering checks.
• Duplicate values are not addressed; the returned index could be any matching index, the first matching index, or the last matching index.
• The linear-search baseline is not defined precisely, including whether it scans left-to-right and whether it stops at the first match.

Units and conventions

• Array indices are zero-based integer positions.
• n is the nonnegative integer array length; log2(n) is dimensionless and undefined for n=0.
• The array must be sorted according to the same comparison relation used for the target.
• Test vectors count one three-way comparison per inspected midpoint and use inclusive bounds lo=0 and hi=n-1.
• The linear baseline is left-to-right linear search, counting one inspected array element per comparison and stopping at the first match.

Inspectable vector

One of 4 source-bound review vectors:

{
  "inputs": {
    "array": [
      2,
      5,
      8,
      12,
      16,
      21,
      30
    ],
    "target": 16,
    "mid_rule": "floor(lo+(hi-lo)/2)",
    "comparison_counting": "one midpoint inspection",
    "linear_baseline": "left-to-right"
  },
  "expected_outputs": {
    "trace": [
      {
        "step": 1,
        "lo": 0,
        "hi": 6,
        "mid": 3,
        "value": 12,
        "result": "target greater; set lo=4"
      },
      {
        "step": 2,
        "lo": 4,
        "hi": 6,
        "mid": 5,
        "value": 21,
        "result": "target smaller; set hi=4"
      },
      {
        "step": 3,
        "lo": 4,
        "hi": 4,
        "mid": 4,
        "value": 16,
        "result": "found"
      }
    ],
    "index": 4,
    "binary_comparisons": 3,
    "linear_comparisons": 5,
    "claimed_ceil_log2_n": 3
  },
  "working": "n=7. Step 1: mid=floor(0+(6-0)/2)=floor(3)=3; array[3]=12, and 16>12, so lo=4. Step 2: mid=floor(4+(6-4)/2)=floor(5)=5; array[5]=21, and 16<21, so hi=4. Step 3: mid=floor(4+(4-4)/2)=4; array[4]=16, so found at index 4. Binary comparisons=3. Linear search inspects 2, 5, 8, 12, 16: 5 comparisons. ceil(log2(7))=ceil(2.8073549...)=3."
}

Failure boundary

BREAK_CLAIMED · SELF_FLAGGED

The exact N=1 boundary exposes a mismatch between the stated estimate ceil(log2(N))=0 and the actual required comparison count of 1. N=0 also produces an undefined log2(0) result and must be rejected. Midpoint rounding is unspecified for even-length intervals, and floor versus ceil changes the trace and comparison count.

Other records

Sources and evidence

These pointers bind the page to evidence. They do not grant authority or collapse verification into deployment.

• VERIFIED_LEDGER.json
• evidence-tranche6/tranche6-results.json
• BOUNDARY_HAZARD_CATALOG.json