Binary search

Binary search finds a value in a sorted array by repeatedly halving the search range. Compare the target with the middle element; if equal, done; if smaller, search the left half; if larger, the right half. Runs in O(log n) comparisons.

function search(a, x):
    lo = 0; hi = length(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        if a[mid] == x: return mid
        if a[mid] < x: lo = mid + 1
        else: hi = mid - 1
    return not found

The mid computation avoids the overflow bug in the naive (lo + hi) / 2, famously present in Java's library until 2006.

Written for JnanaBase; not copied.