Binary Search analysis
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
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:\[
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 \\
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:])
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'