# Binary Search analysis

Pseudocode:

function binarySearch(a, value, left, right) if right < left return not found mid := floor((right-left)/2)+left if a[mid] = value return mid if value < a[mid] return binarySearch(a, value, left, mid-1) else return binarySearch(a, value, mid+1, right)

Note that mid is defined as

floor((right-left)/2+left

cause if the array is indexed, say, form 4 to 10, the mid is actually

(high - low)/2 + offset

A binary search halves the number of items to check with each iteration, so locating an item (or determining its absence) takes logarithmic time.

A sketch of the proof for N being even is the following: we define \( C(N) \) as the number of compares needed to locate the key in an array of N elements. We start with

\[C(0) = 0 \\

C(1) = 1 \\

C(N) \leq C(N/2) + 1 \\

\]

the number of compares for N is at most N/2 + 1: 1 to check for equality and decide for the left half or the right half. Applying the same logic, we obtain:

\[\begin{align}

C(N/2) + 1 & \leq C(N/4) + 1 + 1 \\

& \leq C(N/8) + 1 + 1 + 1 \\

& \leq C(N/16) + 1 + 1 + 1 + 1 \\

& \leq C(N/N) + 1 + 1 + 1 + 1 + … + 1 \\

& = 1 + \log N \\

\end{align}

\]

At that point we stop since C(1) = 1, giving us the number of times we had to halve the space search to get to N.

Implementation in Python: recursive

def bs(n, l): if len(l) < 1: return 'not found' mid = len(l)/2 if l[mid] == n: return l[mid] elif n < l[mid]: return bs(n, l[:mid]) else: return bs(n, l[mid+1:])

iterative:

def ibs(n, l): imin = min(l) imax = max(l) while imax > imin: imid = (imax - imin)/2 + imin if l[imid] == n: return l[imid] elif n < l[imid]: imax = imid - 1 else: imin = imid + 1 return 'not found'