the RIGHT Binary Search

bs.py

"""
binary search
"""


def binary_search(num_array, x):
    l = 0
    r = len(num_array)
    while l < r:
        mid = l + (r - l) / 2
        if num_array[mid] >= x:
            r = mid
        else:
            l = mid + 1
    return l


if __name__ == '__main__':
    assert 1 == binary_search([1], 9)
    assert 0 == binary_search([1], -1)
    assert 1 == binary_search([0, 1, 1, 3, 4, 5], 1)
    assert 6 == binary_search([0, 1, 1, 3, 4, 5], 10)