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 L^{\prime },v^{\prime }\exists 0\le b\le e\le |L^{\prime }|\wedge 0\le e-b<m$$

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

termination bound function: $e-b$

Complexity:

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

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

$$x+2={\log }_2(n)+2\to \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