1

Моя задача: Для каждого элемента из списка b вывести индекс j из списка A, если b[i]=A[j], если для элемента из списка b нет такого элемента в списке A, то вывести -1. то есть вывод должен быть такой: 3 1 -1 1 -1

В коде 1 у меня цикл выполняется бесконечно, однако в коде 2 я каждый элемент из списка b проверил вручную и ответы были верными.

Код 1

def same_numb():
    n=5
    A = [1, 5, 8, 12, 13]
    k=5
    b = [8, 1, 23, 1, 11]
    spis = []
    for i in range(0, k-1):
        # левая граница
        l=1
        # правая граница
        r=n
        # если b[i]==A[0], то в цикл while не заходим
        if b[i]==A[0]:
            spis.append(0)
            l=r+1
        while l<=r:
            # середина списка m
            m=int(l+(r-l)/2)
            if A[m]==b[i]:
                spis.append(m)
            elif A[m]>b[i]:
                r=m-1
            else:
                l=m+1
            if l>r:
                spis.append(-1)
                break
    return spis

Код 2

C=[1, 5, 8, 12, 13]
k=8
def ff():
    l=1
    r=n
    if k==C[0]:
        return 0
    if k>C[4]:
        return -1
    while l<=r:
        m=int(l+(r-l)/2)
        if C[m]==k:
            return m
        elif C[m]>k:
            r=m-1
        else:
            l=m+1
    return -1
2
  • это задача такая стоит - использовать бинарный поиск?
    – Zhihar
    6 фев 2021 в 11:16
  • ваша ошибка if A[m]==b[i]: spis.append(m) вы бесконечно апендите по кругу и всё. break спасёт мир ) в коде2 у вас там return кстати.
    – Интик
    6 фев 2021 в 11:37

2 ответа 2

1

а так работает?

A = [1, 5, 8, 12, 13]
B = [8, 1, 23, 1, 11]

spis = []

# проанализировать все элементы списка b
for elem in B:

    # границы
    left = 0
    right = len(A) - 1

    # поиск
    while True:
        # середина списка m
        middle = (left + right) // 2

        if middle == left or middle == right:
            break

        if A[middle] > elem:
            right = middle
        else:
            left = middle

    # добавить позицию
    spis.append(-1 if A[left] != elem else left)

print(spis)

или так, если брать код бинарного поиска из интернета:

# проанализировать все элементы списка b
for elem in B:

    # границы
    left = 0
    right = len(A)
    middle = 0

    # поиск
    while left <= right:
        # середина списка m
        middle = (left + right) // 2

        if middle == left or middle == right:
            break

        if elem < A[middle]:
            right = middle - 1
        else:
            left = middle + 1

    # добавить позицию
    spis.append(-1 if A[right - 1] != elem else right - 1)
0
  1. Двоичный поиск применим только к отсортированным массивам.
  2. Эта задача решается куда проще:
def same_numb(A, b):
    res = []
    for x in b:
        res.append(A.index(x))
    return res

Или вообще в одну строку:

res = [A.index(x) for x in b]

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.