Бинарный поиск

@Xeib9 · Регистрация: 11.04.2020

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

Реализуйте алгоритм бинарного поиска.

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

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

Примеры
Входные данные
10 5
1 2 3 4 5 6 7 8 9 10
-2 0 4 9 12

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

Необходимо как можно быстрее по времени и именно бинарный поиск.

@Fury67 · 22.04.2020, 22:20

Ну бинарный поиск сами реализуйте, мне это слишком скучно. А так, способ решения вашей задачи в одну строку ловите.

Python

1	(lambda a, b: print( [ "Yes" if a.count(b[i]) != 0 else "No" for i in range(len(b))])) ((list(map(int,iter(input,'')))), (list(map(int,iter(input,'')))))

Ввод каждого элемента массива в новой строке до пустой строки. Ввод массивов друг за другом.
Пример:
Ввод:
1
2
3

2
3
4

Вывод:
['Yes', 'Yes', 'No']

Добавлено через 2 минуты
Xeib9, если будут конкретные вопросы по бинарному поиску, то пишите. Код за вас писать никто не будет. Только ваш код подправить могу. Присылайте код.

@eaa · 23.04.2020, 10:00

зачем писать?!
https://docs.python.org/3/library/bisect.html

Новые блоги и статьи
Как написать микросервис на Go/Golang InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .
Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .	Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .	Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь! Hrethgir 13.01.2025 По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта в Gowin Eda. Восьмибитный счётчик из сумматора+ генератор сигнала. . .	UserScript для подсветки кнопок языков программирования в зависимости от текущего раздела volvo 13.01.2025 В результате работы этого скрипта подсвечиваются нужные кнопки не только в форме быстрого ответа, но и при редактировании сообщения: / / ==UserScript== / / @name CF_DefaultLangSelect / / . . .	Введение в модели и алгоритмы машинного обучения InfoMaster 12.01.2025 Машинное обучение представляет собой одну из наиболее динамично развивающихся областей искусственного интеллекта, которая фокусируется на разработке алгоритмов и методов, позволяющих компьютерам. . .	Как на Python создать нейросеть для решения задач InfoMaster 12.01.2025 В контексте стремительного развития современных технологий особое внимание уделяется таким инструментам, как нейросети. Эти структуры, вдохновленные биологическими нейронными сетями, используются для. . .

@Xeib9 0 / 0 / 0 Регистрация: 11.04.2020 Сообщений: 8
		1
	Бинарный поиск 22.04.2020, 21:36. Показов 931. Ответов 2 Метки python3.x (Все метки) Реализуйте алгоритм бинарного поиска. Входные данные В первой строке входных данных содержатся натуральные числа N и K (0<N;K<=100000 ). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке – K элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 10⁹ Выходные данные Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае. Примеры Входные данные 10 5 1 2 3 4 5 6 7 8 9 10 -2 0 4 9 12 Выходные данные NO NO YES YES NO Необходимо как можно быстрее по времени и именно бинарный поиск. 0

@eaa Status 418 4580 / 2348 / 601 Регистрация: 26.11.2017 Сообщений: 5,264 Записей в блоге: 3
	23.04.2020, 10:00	3
	зачем писать?! https://docs.python.org/3/library/bisect.html 0

Опции темы