Binary Search (Iterative)

Locate a target value in a sorted array by halving the search window each step. After every probe, either the target is at mid or the window shrinks to its left or right half.

Algorithm

Canonical input arr=(1 3 5 7 9 11 13) with target=11 finishes in two probes; the matching 0-indexed position is 5.

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 bsearch(lo, hi, result) AS (
  SELECT 0, (SELECT COUNT(*) - 1 FROM arr), -1
  UNION ALL
  SELECT
    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 bsearch
  WHERE result = -1 AND lo <= hi
)
SELECT MAX(result) FROM bsearch;

Complexity

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

Implementation notes

SQL: the sorted array becomes arr(idx INTEGER PRIMARY KEY, val INTEGER), and the search state (lo, hi, result) is carried by a WITH RECURSIVE bsearch CTE. Each recursive step reads arr.val at the midpoint via a scalar subquery and updates lo, hi, and result with three parallel CASE expressions.
The WHERE result = -1 AND lo <= hi guard on the recursive arm ends the loop as soon as the target is found or the window collapses. SELECT MAX(result) FROM bsearch then projects the matching index out of the result set; a no-match search would return -1 instead.
The midpoint formula lo + (hi - lo) / 2 uses SQLite's integer division to mirror the int semantics of the other DSA books.

midpoint probe Compute `mid = lo + (hi - lo) / 2` to avoid the overflow trap of `(lo + hi) / 2` on large ranges.

window halving On a mismatch, drop the half that cannot contain the target.