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.

Basic Implementation

basic.sql 
.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;

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