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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .

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

	Двоичный поиск 17.07.2020, 19:53. Показов 2796. Ответов 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