Arrays and Iteration

Linear Search

Walk an array once looking for a target value. Return the index of the first match, or -1 if none. The simplest possible search loop.

Algorithm

Canonical input arr=(4 7 1 9 3 8) with target=9 finishes after four compares; the matching 0-indexed position is 3.

early exit Return the index the moment `arr[idx]` equals the target. Walking past it would defeat the point.
sentinel return A no-match walk falls off the loop and returns `-1`.

Basic Implementation

basic.sql
Replay: real traced execution (multi-file project)
.mode list
.headers off
CREATE TABLE arr(idx INTEGER PRIMARY KEY, val INTEGER);
INSERT INTO arr(idx, val) VALUES
  (0, 4), (1, 7), (2, 1), (3, 9), (4, 3), (5, 8);
WITH RECURSIVE scan(idx, match_idx) AS (
  SELECT 0, CASE WHEN (SELECT val FROM arr WHERE idx = 0) = 9 THEN 0 ELSE -1 END
  UNION ALL
  SELECT scan.idx + 1,
         CASE WHEN scan.match_idx >= 0 THEN scan.match_idx
              WHEN arr.val = 9 THEN scan.idx + 1
              ELSE -1 END
  FROM scan JOIN arr ON arr.idx = scan.idx + 1
  WHERE scan.match_idx < 0
)
SELECT COALESCE(MAX(match_idx), -1) FROM scan;

  1. arr ← (empty)

    1.mode list2.headers off
    values this step(empty)arr

  2. arr ← [4, 7, 1, 9, 3, 8], target ← 9

    1.mode list2.headers off
    values this step(empty) → [4, 7, 1, 9, 3, 8]arr9target

  3. scan.idx ← 1

    1.mode list2.headers off
    values this step0 → 1scan.idx4arr.val-1scan.match_idx

  4. scan.idx ← 2

    1.mode list2.headers off
    values this step1 → 2scan.idx7arr.val-1scan.match_idx

  5. scan.idx ← 3

    1.mode list2.headers off
    values this step2 → 3scan.idx1arr.val-1scan.match_idx

  6. scan.idx ← 4, scan.match_idx ← 3

    1.mode list2.headers off
    values this step3 → 4scan.idx-1 → 3scan.match_idx9arr.val

  7. stdout ← 3

    1.mode list2.headers off
    values this step3stdout3scan.match_idx

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • SQL: the array becomes arr(idx INTEGER PRIMARY KEY, val INTEGER) and the scan is a WITH RECURSIVE CTE that carries (idx, match_idx). match_idx starts at -1, flips to the matching index on the frame where arr.val = 9, and is sticky from then on. A plain SELECT idx FROM arr WHERE val = 9 would skip the iteration the lesson is teaching by handing the whole array to the query planner instead of stepping through it.
  • The WHERE scan.match_idx < 0 clause on the recursive arm acts as the early-exit guard: the recursion stops feeding new rows the moment a match is found, which mirrors return in an imperative loop.
  • COALESCE(MAX(match_idx), -1) at the bottom emits the canonical 3 for the lesson input, and would emit the canonical sentinel -1 if the search ran off the end.