Ошибка в двоичном поиске

Question

Понимаю логику программы, но не понимаю ошибку...

По моим размышлениям я считываю размеры списков, сами списки и просто передвигаю метку, сравнивая что находится слева и справа от нее. Многого не знаю. поэтому прошу помощи и как можно более разжеванную

Ввожу:

10 10

1 61 126 217 2876 6127 39162 98126 712687 1000000000 

100 6127 1 61 200 -10000 1 217 10000 1000000000

a, b = map(int, input().split())
elem = [input().split(), int]
zap = [input().split(), int]

for i in zap:
    le = 0
    r = len(elem)

    while 1 < r - le:
        m = (le + r) // 2

        if elem[m] < i: # TypeError: '<' not supported between instances of 'type' and 'list'
            le = m
        elif elem[m] == zap[i]:
            print("Yes")
            break
        else:
            r = m

Answer 1

a, b = map(int, input().split())

Переменные a и b вы никак не используете, поэтому эта строчка вообще не нужна.

elem = [input().split(), int]
zap = [input().split(), int]

Тут вы делаете что-то непонятное - создаёте список, внутри которого первым элементом идёт список, полученный разбиением ввода, а второй элемент - тип int. Из-за чего у вас потом и выходит ошибка - вы сравниваете тип со списком. Вместо этого нужно разбивать ввод на элементы и приводить их к типу int вот так:

elem = list(map(int, input().split()))
zap = list(map(int, input().split()))

Далее вы итерируетесь по списку и используете элемент списка в качестве индекса в этом же списке:

for i in zap:
    ^^^^^^^^
    ...
    elif elem[m] == zap[i]:
                    ^^^^^^

Естественно, это приводит к ошибке - у вас же всего 10 элементов в списке, а не 100 и не 6127. Сравнивать надо сам элемент списка в этом случае, так же, как это у вас сделано чуть выше для сравнения <:

    elif elem[m] == i:

После этого всё работает. Ввод:

1 61 126 217 2876 6127 39162 98126 712687 1000000000
100 6127 1 61 200 -10000 1 217 10000 1000000000

Вывод:

Yes 6127
Yes 61
Yes 217
Yes 1000000000

БЛОГ НА HUSL

Ошибка в двоичном поиске

Ответы (1 шт):