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.

   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.