# 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|

ifn= 0

returnNone

m←ndiv 2

ifa[m] =e:

returnm

ifa[m] <e:

p←binary_search(a[m+1..n],e)

ifp=None:

returnNone

returnm+ 1 +p

returnbinary_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.