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'