Fundamentals

See also: complexity analysis

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

recursive binary search:

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 → 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$

Theorem

LowerBoundRec is correct and runtime and memory complexity of $\Theta(\log_2(|L|))$

non-recursive binary search:

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