Двоичный поиск

@Russia_top · Регистрация: 12.07.2020

Студворк — интернет-сервис помощи студентам

Двоичный поиск
В данной задаче можно пользоваться встроенными функциями.

Входные данные

В первой строке входных данных содержатся натуральные числа N и K (0<N,K≤100000). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке — K элементов второго массива. Элементы обоих массивов — целые числа, каждое из которых по модулю не превосходит 109.

Выходные данные

Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.
Помогите, пожалуйста, решить!

@Dax · 18.07.2020, 11:19

Так?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import random
 
 
def masgen(n, k):
    # print(n)
    # print(k)
    mlist = [random.randint(1, 10) for i in range(n)]
    mlist.sort(reverse=False)
    print(*mlist)
    mlist1 = [random.randint(1, 10) for i in range(k)]
    mlist1.sort(reverse=False)
    print(*mlist1)
    for i in mlist1:
        if i in mlist:
            print('yes')
        else:
            print('no')
 
 
if __name__ == '__main__':
    n, k = map(int, input().split())
 
    masgen(n, k)

@Russia_top · 18.07.2020, 14:34 **[ТС]**

Dax, Пишет программа выполнялась слишком долго

@Gdez · 18.07.2020, 18:52

Python
1
2
for c in mlist1 :
    print (str('NO') if bisect_left(mlist,c) - bisect_right(mlist,c) == 0 else str('YES'))

Вас тролят - нужно хоть что то свое предлагать...

@Dax · 18.07.2020, 21:05

Сообщение от Gdez

нужно хоть что то свое предлагать.

Gdez, Ваши бы слова, да Богу в уши....

@weatherReport · 19.07.2020, 18:54

А что подразумевается под переменной mlist1?

@Gdez · 19.07.2020, 19:26

Из условия задачи - второй массив

Новые блоги и статьи Все статьи Все блоги /
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ

@Russia_top 1 / 1 / 0 Регистрация: 12.07.2020 Сообщений: 42

	Двоичный поиск 17.07.2020, 19:53. Показов 2801. Ответов 6 Метки питон (Все метки) Двоичный поиск В данной задаче можно пользоваться встроенными функциями. Входные данные В первой строке входных данных содержатся натуральные числа N и K (0<N,K≤100000). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке — K элементов второго массива. Элементы обоих массивов — целые числа, каждое из которых по модулю не превосходит 109. Выходные данные Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае. Помогите, пожалуйста, решить! 0

@Russia_top 1 / 1 / 0 Регистрация: 12.07.2020 Сообщений: 42
	18.07.2020, 14:34 [ТС]
	Dax, Пишет программа выполнялась слишком долго 0

@weatherReport 14 / 14 / 0 Регистрация: 03.04.2020 Сообщений: 16
	19.07.2020, 18:54
	А что подразумевается под переменной mlist1? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	19.07.2020, 19:26
	Из условия задачи - второй массив 0