Searching

Binary Search First Occurrence

Find the first copy of a duplicated target by recording matches and continuing to search the left half.

Algorithm

execution replay The checked-in replay follows the language-neutral state table for `search-binary-first`.
cross-language comparison This SQL DSA version keeps the same data and final output as every other DSA book in this wave.

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, 1), (1, 2), (2, 4), (3, 4), (4, 4), (5, 7), (6, 9);
WITH RECURSIVE search(step, lo, hi, result) AS (
  SELECT 0, 0, 6, -1
  UNION ALL
  SELECT
    step + 1,
    CASE WHEN (SELECT val FROM arr WHERE idx = lo + (hi - lo) / 2) < 4
         THEN lo + (hi - lo) / 2 + 1 ELSE lo END,
    CASE WHEN (SELECT val FROM arr WHERE idx = lo + (hi - lo) / 2) >= 4
         THEN lo + (hi - lo) / 2 - 1 ELSE hi END,
    CASE WHEN (SELECT val FROM arr WHERE idx = lo + (hi - lo) / 2) = 4
         THEN lo + (hi - lo) / 2 ELSE result END
  FROM search
  WHERE lo <= hi
)
SELECT result FROM search ORDER BY step DESC LIMIT 1;

  1. arr ← [1, 2, 4, 4, 4, 7, 9], target ← 4, result ← -1

    1.mode list2.headers off
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

  2. hi ← 2, mid ← 3, result ← 3

    1.mode list2.headers off
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    1.mode list2.headers off
    values this step0 → 2lo1mid2hi3result

  4. hi ← 1, result ← 2, mid ← 2

    1.mode list2.headers off
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    6WITH RECURSIVE search(step, lo, hi, result) AS (7  SELECT 0, 0, 6, -18  UNION ALL
    values this step2stdout2result

Complexity

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

Implementation notes

  • Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
  • The final output is intentionally small and deterministic for cross-language comparison.