Source: https://guthlabs.ai/docs/instruments/binary-search-sorted-array-step-visualizer/mechanism/

instrument mechanism / verified-clean

# Binary Search / Sorted-Array Step Visualizer mechanism

The inspectable method record for Binary Search / Sorted-Array Step Visualizer, kept separate from implementation and qualification.

Status: **VERIFIED_CLEAN**Lifecycle: **verified-clean**

## 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

[01**Overview**](<https://guthlabs.ai/docs/instruments/binary-search-sorted-array-step-visualizer/>)[03**Implementation**](<https://guthlabs.ai/docs/instruments/binary-search-sorted-array-step-visualizer/implementation/>)[04**Qualification**](<https://guthlabs.ai/docs/instruments/binary-search-sorted-array-step-visualizer/qualification/>)

## 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`