Как определить инвариант алгоритма python binsearch из lib?

petrush спросил: 14 ноября 2017 в 07:13 в: python

Я нашел следующий код в Python lib:

def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

Вернуть индекс, куда вставить элемент x в список a, при условии, что a отсортировано. Возвращаемое значение i таково, что все e в [: i] имеют e < x, и все e ina [i:] имеют e > = x.

Что является инвариантом этого алгоритма? Я хочу понять, что это правильно.

0 ответов