---
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
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
---
See also: [[thoughts/university/twenty-three-twenty-four/sfwr-2c03/W1#complexity|complexity analysis]]

`LinearSearch(L, v, o)`: potentially-high cost

### _recursive binary search:_

```prolog
LowerBoundRec(L, v, begin, end)
# Input: L: ordered array, v: value, 0 <= begin <= end <= |L|
if begin = end then
  return begin
else
  mid := (begin + end) div 2
  if L[mid] < v then
    return LowerBoundRec(L, v, mid+1, end)
  else if L[mid] >= v then
    return LowerBoundRec(L, v, begin, mid)
# Result: return first offset r, begin <= r <= end with L[r] = v, or no such offset exists, r = |L|
```

> repetition <span>&rarr;</span> induction

Induction hypothesis:

$$
\forall \space L', v' \space \exists \space  0 \leq b \leq e \leq |L'| \land 0 \leq e - b < m
$$

Recursive case: `mid := (begin + end) div 2`: $b \leq \text{mid} < e$

termination bound function: $e - b$

Complexity:

$$
T(n) = \begin{cases}
    1 & \text{if } n = 0;\\\
    1 \cdot T(\lfloor \frac{n}{2} \rfloor) + 1 & \text{if } n > 1. \\\
\end{cases}
$$

Complexity: $T(n) = 1 \cdot T(\lfloor \frac{n}{2} \rfloor) + 1$. Assume $n=2^x$, work = 1

$$
x+2 = \log_2(n) + 2 \rightarrow \Theta(\log_2(n))
$$

> Can usually assume $n=2^x$

> \[!abstract\] Theorem
>
> `LowerBoundRec` is correct and runtime and memory complexity of $\Theta(\log_2(|L|))$

### _non-recursive binary search:_

```prolog
LowerBound(L, v, begin, end)
# Input: L: ordered array, v: value, 0 <= begin <= end <= |L|
while begin < end do
  mid := (begin + end) div 2
  if L[mid] < v then
    begin := mid + 1
  else
    end := mid
return begin
```