# Binary Search analysis

Pseudocode:

function binarySearch(a, value, left, right)
if right < left
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:

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