Searching

Binary Search (Recursive)

Use the same binary-search window as the iterative lesson, but pass lo and hi through recursive calls.

Algorithm

execution replay The checked-in replay follows the language-neutral state table for `search-binary-recursive`.
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, 3), (2, 5), (3, 7), (4, 9), (5, 11), (6, 13);
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) < 11
         THEN lo + (hi - lo) / 2 + 1 ELSE lo END,
    CASE WHEN (SELECT val FROM arr WHERE idx = lo + (hi - lo) / 2) > 11
         THEN lo + (hi - lo) / 2 - 1 ELSE hi END,
    CASE WHEN (SELECT val FROM arr WHERE idx = lo + (hi - lo) / 2) = 11
         THEN lo + (hi - lo) / 2 ELSE result END
  FROM search
  WHERE result = -1 AND lo <= hi
)
SELECT result FROM search WHERE result != -1 ORDER BY step DESC LIMIT 1;

  1. lo ← 0, hi ← 6, target ← 11

    1.mode list2.headers off
    values this step0lo6hi11target

  2. mid ← 3, arr[mid] ← 7, next call ← (4, 6)

    1.mode list2.headers off
    values this step3mid7arr[mid](4, 6)next call0lo6hi

  3. mid ← 5, arr[mid] ← 11, result ← 5

    1.mode list2.headers off
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

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

Complexity

  • Time: O(log n)
  • Space: O(log n) call stack

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.