---
date: '2024-01-15'
description: binary search fundamentals with recursive and iterative implementations, complexity analysis, and logarithmic runtime proofs.
id: W2
modified: 2026-06-05 15:08:41 GMT-04:00
seealso:
  - '[[thoughts/university/twenty-three-twenty-four/sfwr-2c03/W1#complexity|complexity analysis]]'
tags:
  - sfwr2c03
title: Fundamentals
created: '2024-01-15'
published: '2024-01-15'
pageLayout: default
slug: thoughts/university/twenty-three-twenty-four/sfwr-2c03/W2
permalink: https://aarnphm.xyz/thoughts/university/twenty-three-twenty-four/sfwr-2c03/W2.md
generator:
  quartz: v4.6.0
  hostedProvider: Cloudflare
  baseUrl: aarnphm.xyz
full: https://aarnphm.xyz/llms-full.txt
---
A linear search may inspect every element. A sorted array gives us a reason to discard a whole interval after one comparison: all elements before a value are no larger than it, and all elements after it are no smaller. Binary search chooses the midpoint so that either branch leaves at most half the current elements.[^slides]

Here the task is **lower bound**. Given an array $L$ sorted in nondecreasing order, find the first position in the half-open range $[b,e)$ whose value is at least $v$. Return $e$ if every value in the range is smaller. Equivalently, return the unique boundary $r$ satisfying

$$
\begin{aligned}
&b \le r \le e, \\
&\forall i \in [b,r),\quad L[i] < v, \\
&\forall i \in [r,e),\quad L[i] \ge v.
\end{aligned}
$$

This is also the insertion position before any existing copies of $v$.[^boundary] For $L=[2,4,4,9]$, searching the full array for $4$ returns $1$; searching for $5$ returns $3$; searching for $10$ returns $4$. The middle case shows why an equality-only result contract is wrong. To test membership after finding $r$, check $r<e$ **before** reading $L[r]$, then test $L[r]=v$. The original upper bound $e$ may be smaller than $|L|$ when searching a subrange.

### _recursive binary search:_

Assume $0\le b\le e\le |L|$. The pseudocode uses `begin` and `end` for these bounds:



```text
LowerBoundRec(L, v, begin, end)
  if begin = end then
    return begin
  mid := begin + (end - begin) div 2
  if L[mid] < v then
    return LowerBoundRec(L, v, mid + 1, end)
  else
    return LowerBoundRec(L, v, begin, mid)
```

Equality takes the left branch because an earlier copy may exist. Keeping `mid` as the new upper bound still allows the boundary itself to be `mid`, even though the next search excludes that element. The midpoint expression avoids adding two potentially large indices in a fixed-width implementation.[^boundary]

#### correctness and termination

Prove the boundary contract by strong induction on the range length $n=e-b$.

For $n=0$, the only possible boundary is $b=e$. Returning it satisfies both ordering conditions because both intervals are empty. This also handles an empty array without reading an element.

For $n>0$, assume every valid call on a shorter range returns its lower bound. The midpoint $m$ satisfies

$$
b\le m<e.
$$

If $L[m]<v$, sorted order puts every element from $b$ through $m$ below $v$. The answer lies in $[m+1,e]$, and the induction hypothesis gives that boundary from the recursive call on $[m+1,e)$.

Otherwise $L[m]\ge v$, so every element from $m$ through $e-1$ is at least $v$. The answer lies in $[b,m]$, and the call on $[b,m)$ returns it by the same hypothesis. Either call preserves the discarded side’s ordering condition.

Both branches strictly reduce the nonnegative integer $e-b$, so the calls terminate. In particular, a one-element range makes one comparison and then calls the empty-range case.

#### complexity

Let $W(n)$ count calls on the longest path, including the final empty-range call. Then

$$
W(n)=
\begin{cases}
1, & n=0, \\
W(\lfloor n/2\rfloor)+1, & n\ge 1.
\end{cases}
$$

The $n=1$ case belongs in the recurrence. For $n=2^k$, the longest path visits lengths

$$
2^k,\;2^{k-1},\;\ldots,\;1,\;0,
$$

giving $k+2$ calls. For any positive integer $n$, repeated floor-halving gives $\lfloor\log_2 n\rfloor+2$ calls on the longest path. This establishes the bound without assuming that every input length is a power of two.

> \[!abstract\] Theorem
>
> With constant-time array access and comparisons, the recursive lower-bound algorithm takes $\Theta(\log(n+1)+1)$ time and the same amount of auxiliary stack space without tail-call optimisation. Here $n=e-b$. This form includes the constant-cost empty range; for $n\ge2$ the bound is usually written $\Theta(\log n)$.

### _non-recursive binary search:_

The loop keeps the same boundary contract while changing its working bounds:



```text
LowerBound(L, v, begin, end)
  while begin < end do
    mid := begin + (end - begin) div 2
    if L[mid] < v then
      begin := mid + 1
    else
      end := mid
  return begin
```

Relative to the original range $[b,e)$, all values before the current `begin` are below $v$, and all values from the current `end` onward are at least $v$. At exit the working bounds coincide, so that index separates the two parts. The same decreasing range length proves termination. Runtime remains $\Theta(\log(n+1)+1)$, and auxiliary space is $\Theta(1)$ because the loop stores a fixed number of indices.

[^slides]: Jelle Hellings, [[thoughts/university/twenty-three-twenty-four/sfwr-2c03/binary-search.pdf|Fundamentals: binary-search slides]], slides 4–9 (PDF pages 7–34, including animation repeats). The algorithms find an insertion boundary. The slides’ equality-only result statement needs the separate membership check given here.

[^boundary]: Paulo Feofiloff, University of São Paulo, [Searching sorted arrays](https://www.ime.usp.br/~pf/algorithms/chapters/binary-search.html), sections “The search problem”, “Is the function binarysearch correct?” and “Exercises 6”, for the insertion boundary, end-position interpretation and half-open loop variant; “Exercises 4” flags midpoint overflow.