Binary Search

Tags

algorithm

An algorithm for finding a value in a sorted collection, which at each step cuts the space to be searched in half.

This algorithm works on the assumption that for 3 values in the sorted array \( i, j, k \; i < j < k \), if \( a[i] < a[j] \) then \( a[i] < a[k] \). I.E. transitivity. From this if we're trying to find a value \( x \) in the array and we find that \( a[i] < x \) then we know whatever position in the array where \( x \) can be found must be at a position greater than \( i \) and therefore the subset of the array that's less than \( i \) doesn't need to be checked anymore.

n = len(arr)
i, j = 0, n - 1
while i <= j:
    mid = (i + j) / 2
    if arr[mid] > x:
	j = mid + 1
    elif arr[mid] < x:
	i = mid - 1
    else:  # arr[mid] == x:
	return mid
return -1

The specific algorithm can be seen in alg:bin-search. It begins by specifying a range of values in the array \( [i, j] \) which is our effective search space. Each loop we pick the value at the middle of this search space, effectively the value equidistant from both ends of it, and then check whether the current value is the one we're searching for. If it is we exit, we've found the correct value. If it isn't we clamp the range to either \( (\text{mid}, j] \) or \( [i, \text{mid}) \) depending on whether the value is larger or smaller than the one we're searching for. This process repeats until the invariant of the loop \( i \leq j \) is invalidated, at which point we've considered every value in the array (either directly or transitively) but failed to find what we're searching for, meaning it doesn't exist.