DjangoBB LoFi version

Полная версия: Помогите с бинарным поиском

Начало » Python для новичков » Помогите с бинарным поиском

Fronior

Май 17, 2017 21:35:22

Программа на вход получает два массива. Необходимо узнать, есть ли элемент второго списка в первом списке. Если элемент имеется, то вывести YES, а если нет, то NO
У меня почему-то анализируется только два элемента. Пожалуйста, укажите мне на мою ошибку.
A = list(map(int, input().split()))
B = list(map(int, input().split()))
for x in B:
i = 0
j = len(A)-1
m = int(j/2)
while A != x and i < j:
if x > A:
i = m+1
else:
j = m-1
m = int((i+j)/2)
if i > j:
print('NO')
else:
print('YES')

py.user.next

Май 18, 2017 01:34:14

Fronior
Пожалуйста, укажите мне на мою ошибку.

Массив должен быть отсортирован. Используй только циклы while.

Код на C на основе кода из K&R2 (выполненное задание)

/* binsearch: поиск x в v[0] <= v[1] <= ... <= v[n - 1];
              версия с одной проверкой в цикле */
int binsearch(int x, int v[], int n)
{
    int low, high, mid;

    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return (v[high] == x) ? high : -1;
}