Бинарный поиск. Переполнение памяти и большое время выполнения программы

Была проблема а том что выполнялся линейный алгоритм, а надо было логарифмический, для того чтобы выполнялся логарифмический я использовал бинарный поиск, также я убрал метод count (), который из логарифмического делал линейный алгоритм

'''Код отредактированный'''

def left_binarnui_poisk (a,value): # левый бинарный поиск
    result = -1
    low = 0
    high = len(a) - 1
    mid = len(a) // 2

    while low <= high:
        if value == a[mid]:
            high = mid - 1
            result = mid + 1
        elif value > a[mid]:
            low = mid + 1
        else:
            high = mid - 1

        mid = (low + high) // 2
    return result


def right_binarnui_poisk (a,value): # правый бинарный поиск
    result = -1
    low = 0
    high = len(a) - 1
    mid = len(a) // 2

    while low <= high:
        if value == a[mid]:
            low = mid + 1
            result = mid + 1
        elif value > a[mid]:
            low = mid + 1
        else:
            high = mid - 1

        mid = (low + high) // 2
    return result



#ввод данных
N, K = map(int, input().split())
sp = [int(i) for i in input().split()]
sp1_ = [int(i) for i in input().split()]


# организация вывода
for i in range(K):
    result_itog = [left_binarnui_poisk(sp,sp1_[i]),right_binarnui_poisk(sp,sp1_[i])]
    if result_itog.count(-1): # если вывод равен [-1,-1], то выведет 0 по условию задачи
        print(0)
    else:
        print(*result_itog)

Мне не нравится ответ автора вопроса. Не потому что он не правильный. Я его не тестировал, очевидных ошибок я нём не вижу. Мне он не нравится потому что использует странный дизайн: переменная result, две проверки условия на цикл, отсутствие утверждений об инвариантах.

Мой вариант всегда возвращает позицию i для вставки элемента v в упорядоченный список a, такую что a[:i] + [v] + a[i:] сохраняет порядок. Если в списке a есть одна или несколько таких позиций, bisect_left возвращает минимальный такой индекс - самую левую позицию, bisect_right возвращает максимальный индекс - самую правую позицию. Если обе функции вернули одинаковые значения, элемент v в списке отсутствует.

Обе функции нафаршированы закомментированными утверждениями об инвариантах. Закомментированными потому что любое такое утверждение увеличивает время работы функции c log n до n log n.

В каждом цикле делается только одно сравнение. Это увеличивает производительность. Обычно второе условие проверяет равенство для раннего выхода из цикла. Можно показать что эта оптимизация экономит в среднем одну итерацию, увеличивая количество проверок в два раза. То есть, она замедляет поиск.

def bisect_left(a, v):
    low = 0
    high = len(a)
    # assert a[:low] < v <= a[high:]

    while low < high:
        # assert a[:low] < v <= a[high:]
        mid = (low + high) // 2
        assert low <= mid < high
        if a[mid] < v:
            # assert a[:mid + 1] < v
            low = mid + 1
            # assert a[:low] < v
        else:
            # assert v <= a[mid:]
            high = mid
            # assert v <= a[high:]
        # assert a[:low] < v <= a[high:]

    # assert a[:low] < v <= a[high:]
    assert low == high
    return low


def bisect_right(a, v):
    low = 0
    high = len(a)
    # assert a[:low] <= v < a[high:]

    while low < high:
        # assert a[:low] <= v < a[high:]
        mid = (low + high) // 2
        assert low <= mid < high
        if v < a[mid]:
            # assert v < a[mid:]
            high = mid
            # assert v < a[high:]
        else:
            # assert a[:mid + 1] <= v
            low = mid + 1
            # assert a[:low] <= v
        # assert a[:low] <= v < a[high:]

    # assert a[:low] <= v < a[high:]
    assert low == high
    return low


def bisect_range(a, v):
    return bisect_left(a, v), bisect_right(a, v)


def main():
    _, k = map(int, input().split())
    a = tuple(map(int, input().split()))
    for v in map(int, input().split()):
        left, right = bisect_range(a, v)
        if left == right:
            print(0)
        else:
            print(left + 1, right)


main()

P.S. Это всё сделано для только для упражнения. Функции bisect.bisect_left, bisect.bisect_right есть в стандартной библиотеке.

P.P.S. bisect_left и bisect_right почти одинаковы. Их можно объединить в одну функцию, которая вместо значения v принимает функцию-предикат p. Код сократится. Не знаю можно ли сказать что он станет проще, но отлаживать его будет легче.

def bisect_pred(a, p):
    low = 0
    high = len(a)
    # assert not p(a[:low]) and p(a[high:])

    while low < high:
        # assert not p(a[:low]) and p(a[high:])
        mid = (low + high) // 2
        assert low <= mid < high
        if p(a[mid]):
            # assert p(a[mid:])
            high = mid
            # assert p(a[high:])
        else:
            # assert not p(a[:mid + 1])
            low = mid + 1
            # assert not p(a[:low])
        # assert not p(a[:low]) and p(a[high:])

    # assert not p(a[:low]) and p(a[high:])
    assert low == high
    # assert not p(a[:low]) and p(a[low:])
    return low


def bisect_range(a, v):
    return (
        bisect_pred(a, lambda a_i: a_i >= v),  # bisect_left
        bisect_pred(a, lambda a_i: a_i >  v)   # bisect_right
    )