Searching

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

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;

The pinned run searches for 11 in [1, 3, 5, 7, 9, 11, 13]. The diagrams highlight the inclusive [lo, hi] window and each midpoint.

Step 1 - First midpoint is too small

lo = 0, hi = 6, mid = 3, and arr[3] = 7 is below target 11.

Probe 1 keeps the right half.i0i1i2i3i4i5i6135791113lomidtargethi

Step 2 - Window narrows to the right

Because 7 < 11, set lo = 4 and keep hi = 6.

After discarding indexes 0 through 3.i0i1i2i3i4i5i6135791113discarddiscarddiscarddiscardlomidhi

Step 3 - Second midpoint matches

Now mid = 5 and arr[5] = 11, so the algorithm returns index 5.

Probe 2 finds target 11 at index 5.i4i5i6return911135lomid == targethiindex

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.