Binary Search (Recursive)

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

Algorithm

Basic Implementation

basic.sql

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

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.

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.