def binary_search(haystack, needle, lo, hi):
    """
    Binary search: Return index of value needle (or the next one if no exact
    match) in array haystack, within index range lo to hi.
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if haystack[mid] > needle:
            hi = mid
        elif haystack[mid] < needle:
            lo = mid + 1
        else:
            return mid
    return hi