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:
Recursive case: mid := (begin + end) div 2:
termination bound function:
Complexity:
Complexity: . Assume , work = 1
Can usually assume
Theorem
LowerBoundRecis correct and runtime and memory complexity of
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