w-04-binary-search.yml · YAML

# Binary search: exact-match (chapter 2.1) + rotated-array branch (chapter 2.2)
# Dual-panel shared widget. Chapter 2.1 authors panel-a; chapter 2.2 authors
# panel-b. Both panels populated as of May 2026.

id: w-04-binary-search
title: "Binary search (exact-match + rotated)"
type: dual-panel-shared
level: 1
modes: [preset, randomize, edit]

caps:
  array_length: { min: 1, max: 32 }
  values: { min: -999, max: 999 }
  target: { min: -999, max: 999 }

commands:
  - name: setPointer
    payload: { which: 'lo | hi | mid', index: 'integer | null' }
    description: "Move the named pointer to the given index, or null to clear (lo>hi terminal)."
  - name: compareMid
    payload: { mid: 'integer', value: 'integer', vs_target: 'integer', verdict: 'equal | less | greater' }
    description: "Show the comparison panel under the array; flash the verdict."
  - name: pivotDetect
    payload: { which_sorted: 'left | right', lo_value: 'integer', mid_value: 'integer' }
    description: "Panel-b only. Annotate which half is the monotonic run after the nums[lo] vs nums[mid] check."
  - name: branchDecide
    payload: { sorted_half: 'left | right', in_range: 'boolean', range: 'string' }
    description: "Panel-b only. Show whether target falls in the sorted half's endpoint range."
  - name: narrow
    payload: { side: 'left | right', new_lo: 'integer', new_hi: 'integer' }
    description: "Discard half. left = hi := mid - 1; right = lo := mid + 1."
  - name: found
    payload: { index: 'integer' }
    description: "Hit. Index cell turns solid green; widget enters terminal state."
  - name: absent
    payload: {}
    description: "lo > hi. Interval empty; result -1 displayed in terminal cell."

static_fallback:
  generator: jsdom
  output: site/static/widgets/w-04-binary-search-fallback.svg
  keyframes_used: [0, "n_steps/4", "n_steps/2", "n_steps-1"]
  # Override: the fallback uses the absent-target preset (8 keyframes, 4 picked)
  # because the canonical hit case has only 3 steps - too few for 4 keyframes.

panels:
  panel-a:
    chapter: "2.1"
    label: "Exact-match (closed interval)"
    canonical_input: |
      nums = [1, 3, 5, 7, 9, 11, 13]
      target = 7
    presets:
      - id: canonical-hit
        label: "Canonical (target at median, lucky-mid)"
        input: { nums: [1, 3, 5, 7, 9, 11, 13], target: 7 }
      - id: absent-target
        label: "Target absent (exercises both branches)"
        input: { nums: [1, 3, 5, 7, 9, 11, 13], target: 4 }
      - id: singleton-miss
        label: "Singleton, target absent"
        input: { nums: [5], target: -5 }
      - id: empty-array
        label: "Empty array"
        input: { nums: [], target: 1 }
    n_steps: 8
    # Trace generated for absent-target preset (target=4); the longer of the two
    # canonical traces, exercises every algorithm branch (narrow-left,
    # narrow-right, terminate-empty). Hit case (target=7) is 3 steps.
    keyframes:
      - step: 0
        kind: init
        state: { lo: 0, hi: 6, mid: null, found: false }
        narration: "Closed interval [lo=0, hi=6]. If target 4 exists, it is in nums[0..6]."
      - step: 1
        kind: compareMid
        payload: { mid: 3, value: 7, vs_target: 4, verdict: greater }
        state: { lo: 0, hi: 6, mid: 3, found: false }
        narration: "mid = 0 + (6 - 0)/2 = 3. nums[3] = 7 > 4."
      - step: 2
        kind: narrow
        payload: { side: left, new_lo: 0, new_hi: 2 }
        state: { lo: 0, hi: 2, mid: 3, found: false }
        narration: "Discard right half including mid. hi = mid - 1 = 2."
      - step: 3
        kind: compareMid
        payload: { mid: 1, value: 3, vs_target: 4, verdict: less }
        state: { lo: 0, hi: 2, mid: 1, found: false }
        narration: "mid = 1. nums[1] = 3 < 4."
      - step: 4
        kind: narrow
        payload: { side: right, new_lo: 2, new_hi: 2 }
        state: { lo: 2, hi: 2, mid: 1, found: false }
        narration: "Discard left half including mid. lo = mid + 1 = 2."
      - step: 5
        kind: compareMid
        payload: { mid: 2, value: 5, vs_target: 4, verdict: greater }
        state: { lo: 2, hi: 2, mid: 2, found: false }
        narration: "mid = 2. nums[2] = 5 > 4. Singleton interval, last comparison."
      - step: 6
        kind: narrow
        payload: { side: left, new_lo: 2, new_hi: 1 }
        state: { lo: 2, hi: 1, mid: 2, found: false }
        narration: "hi = mid - 1 = 1. Now lo > hi: closed interval is empty."
      - step: 7
        kind: absent
        payload: {}
        state: { lo: 2, hi: 1, mid: null, found: false, result: -1 }
        narration: "Interval empty. Target absent. Return -1."

  panel-b:
    chapter: "2.2"
    label: "Rotated array (Template A + branch)"
    # Panel-b authored by chapter 2.2. The rotated-array variant adds one
    # comparison against nums[lo] to decide which half is sorted before
    # the standard advance step. Same closed-interval invariant from 2.1.
    canonical_input: |
      nums = [4, 5, 6, 7, 0, 1, 2]
      target = 0
    presets:
      - id: canonical-hit
        label: "Canonical (target in rotated right run)"
        input: { nums: [4, 5, 6, 7, 0, 1, 2], target: 0 }
      - id: target-absent
        label: "Target absent (exercises the branch failure path)"
        input: { nums: [4, 5, 6, 7, 0, 1, 2], target: 3 }
      - id: no-rotation
        label: "Un-rotated (degrades to Template A)"
        input: { nums: [1, 2, 3, 4, 5], target: 4 }
    n_steps: 11
    # Trace generated for canonical-hit preset (target=0). Eleven phase-aware
    # steps: init / compare / pivot-detect / branch-decide / narrow per loop
    # iteration, plus terminal `found`. The rotated branch fires twice in this
    # trace (once with target outside the sorted left, once with target inside).
    keyframes:
      - step: 0
        kind: init
        state: { lo: 0, hi: 6, mid: null, sorted_half: null, found: false }
        narration: "Closed [lo=0, hi=6]. If target 0 lives in nums, its index is in nums[0..6]."
      - step: 1
        kind: compareMid
        payload: { mid: 3, value: 7, vs_target: 0, verdict: greater }
        state: { lo: 0, hi: 6, mid: 3, sorted_half: null, found: false }
        narration: "mid = 0 + (6 - 0)/2 = 3. nums[3] = 7. Not the target."
      - step: 2
        kind: pivotDetect
        payload: { which_sorted: left, lo_value: 4, mid_value: 7 }
        state: { lo: 0, hi: 6, mid: 3, sorted_half: left, found: false }
        narration: "nums[lo]=4 <= nums[mid]=7, so the left half [0..3] is the sorted run."
      - step: 3
        kind: branchDecide
        payload: { sorted_half: left, in_range: false, range: "[4, 7)" }
        state: { lo: 0, hi: 6, mid: 3, sorted_half: left, found: false }
        narration: "Target 0 is not in [4, 7). Discard the sorted left; recurse right."
      - step: 4
        kind: narrow
        payload: { side: right, new_lo: 4, new_hi: 6 }
        state: { lo: 4, hi: 6, mid: 3, sorted_half: left, found: false }
        narration: "lo := mid + 1 = 4. The rotated right run becomes the new search interval."
      - step: 5
        kind: compareMid
        payload: { mid: 5, value: 1, vs_target: 0, verdict: greater }
        state: { lo: 4, hi: 6, mid: 5, sorted_half: null, found: false }
        narration: "mid = 4 + (6 - 4)/2 = 5. nums[5] = 1. Not the target."
      - step: 6
        kind: pivotDetect
        payload: { which_sorted: left, lo_value: 0, mid_value: 1 }
        state: { lo: 4, hi: 6, mid: 5, sorted_half: left, found: false }
        narration: "nums[lo]=0 <= nums[mid]=1, so the left half [4..5] is the sorted run."
      - step: 7
        kind: branchDecide
        payload: { sorted_half: left, in_range: true, range: "[0, 1)" }
        state: { lo: 4, hi: 6, mid: 5, sorted_half: left, found: false }
        narration: "Target 0 is in [0, 1). Recurse into the sorted left this time."
      - step: 8
        kind: narrow
        payload: { side: left, new_lo: 4, new_hi: 4 }
        state: { lo: 4, hi: 4, mid: 5, sorted_half: left, found: false }
        narration: "hi := mid - 1 = 4. Singleton interval; one comparison left."
      - step: 9
        kind: compareMid
        payload: { mid: 4, value: 0, vs_target: 0, verdict: equal }
        state: { lo: 4, hi: 4, mid: 4, sorted_half: null, found: false }
        narration: "mid = 4. nums[4] = 0. Equal to target."
      - step: 10
        kind: found
        payload: { index: 4 }
        state: { lo: 4, hi: 4, mid: 4, sorted_half: null, found: true, result: 4 }
        narration: "Hit. Return 4."

selector_default: panel-a

notes: |
  Combined two-panel cap is 50 steps; panel-a uses 8 (absent preset, the longer
  trace), panel-b uses 11 (canonical hit on the rotated array, exercising both
  branch outcomes). Total 19 steps under the 50-step combined cap.
  The canonical hit preset on panel-a (target=7) produces a 3-step trace too
  short for the 4-keyframe static fallback; the engine uses the absent
  preset's trace for fallback generation regardless of which preset is loaded.
  Chapter 2.1 establishes the exact-match invariant; chapter 2.2 reuses it on
  panel-b with the rotated-half-detection comparison added on top.