|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
02.08.2021, 23:40 | #1 |
Регистрация: 02.08.2021
Сообщений: 4
|
Задача на бинарный поиск
Приветствую всех коллеги, имеется следующая задача:
У вас есть книжная полка, у каждой книги есть размер - количество страниц. Книжная полка представлена массивом, в котором хранятся размеры книг в порядке возрастания. Вам надо написать функцию, которая принимала бы этот массив размеров текущих книг, размер новой книги и вычисляла бы количество больших по размеру книг уже на полке. Требуемая алгоритмическая сложность: время O(log2n), дополнительная память O(1). Реализуйте алгоритм бинарного поиска. С его помощью вы найдёте место в массиве, где слева от него будут элементы меньше или равны, а справа строго больше. Обратите внимание на случай когда у нас на полке есть несколько книг с тем же размером, что и у новой книги. Именно поэтому мы не останавливаем бинарный поиск когда найдём какой-то из таких размеров в массиве, ведь для ответа нам важно чтобы справа от найденной позиции были книги только строго большие по размеру. Продолжать поиск нужно именно бинарным поиском, нельзя просто взять и пройтись вправо по равным элементам до тех пор пока не встретим больший, ведь тогда асимптотика упадёт с O(log2n) до O(n). Моя реализация выглядит следующим образом: Код:
Возможно ли реализовать данный функционал без применения цикла, используя рекурсию? Заранее спасибо. |
02.08.2021, 23:49 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,342
|
Конечно, возможно. Сделайте left и right аргументами функции и вызывайте внутри функцию с новыми границами. Но обычно рекурсию заменяют на цикл, а не наоборот.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
03.08.2021, 00:16 | #3 |
Регистрация: 02.08.2021
Сообщений: 4
|
Да, и действительно можно), сразу не додумался
Код:
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача на линейный и бинарный поиск java | ririta | Общие вопросы по Java, Java SE, Kotlin | 0 | 12.03.2015 13:36 |
Помощь в доработке программы на языке паскаль (бинарный поиск, поиск перебором) | DimzNOVIchok45 | Помощь студентам | 0 | 13.10.2014 20:11 |
Реализовать два метода поиска строк в массиве: поиск перебором, бинарный поиск на языке Pascal | DimzNOVIchok45 | Помощь студентам | 7 | 19.09.2014 21:40 |
C++, задача на бинарный файл (Бинарный файл состоит из записей по 5 бит) | zaitsevmishka | Помощь студентам | 3 | 16.05.2014 21:39 |
Задача на бинарный поиск! | videolord | Общие вопросы по Java, Java SE, Kotlin | 3 | 15.04.2011 00:03 |