Binary Search

Bart Massey

Index Search

• Given: A sequence of values a. A search target e*.

• Find: An index of e in a if present, else None

Captain Obvious's Algorithm: Proceed through a until you either fall off the end or find an e.

Binary Search

• Algorithm for special case of Index Search. Requires that the elements be total-ordered and a be a data structure with fast indexing (usually an array).

• First, sort a (O(|a| lg |a|)).

• Next, "try the middle" repeatedly until either no possible answer or an e is found.

binary_search(a, e):
   n ← |a|
   if n = 0
     return None
   m ← n div 2
   if a[m] = e:
     return m
   if a[m] < e:
     p ← binary_search(a[m+1..n], e)
     if p = None:
       return None
     return m + 1 + p
   return binary_search(a[0..m], e)

• O(lg |a|) search.

Removing Recursion

• Eliminates O(lg |a|) storage requirement. May make it faster.

• First, note that only one recursive call is not "in tail position".

• A call in tail position can effectively be eliminated by a goto, since the return value from the caller will be the same as the return value from the callee.

• That bad call can be transformed to tail-call by introducing some extra arguments.

• While we're at it, we can get replace the array partitioning, which C doesn't support.

• All of this is in Python here.

Binary Search Is Hard

• Bad binary search implementations/algorithms are common.

• Must track invariants carefully. Lots of off-by-one errors.

• Symptoms include infinite looping/recursion, indexing off beginning/end of array.

• This may happen only rarely depending on whether array is odd/even, value is missing at just the wrong spot, etc.

• This is why we start with the recursive definition and transform it.