Source: https://guthlabs.ai/docs/instruments/binary-search-sorted-array-step-visualizer/
instrument / verified-clean
# Binary Search / Sorted-Array Step Visualizer
The current ledger marks this instrument verified clean within the source-bound verification corpus.
Status: **VERIFIED_CLEAN**Lifecycle: **verified-clean**
## Inspectable records
[01**Overview**Purpose and lifecycle]()[02**Mechanism**Method and assumptions]()[03**Implementation**Binding and validation]()[04**Qualification**Evidence and errata]()
## 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`