Binary Search / Sorted-Array Step Visualizer

Inspectable records

Ledger state

The current ledger marks this instrument verified clean within the source-bound verification corpus.

Area

Computing & Information

Tranche

tranche-6

Evidence ID

t6-082

Ledger rows

1

No ledger note is attached.

Review findings

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.

Formula and scope findings

• 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.

Unit assumptions

• 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.

Boundary hardening

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.

Errata and corrections

No applied erratum is attached to this unique-name record.

Inspectable example

4 review vectors are recorded. One source-bound sample is shown below.

{
  "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."
}

Related workflows

No source-defined multi-instrument workflow membership is recorded.

Sources and evidence

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

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