Python бинарный поиск

@IlyaTop · Регистрация: 02.12.2023

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

Девочка загадала число от 1 до N. За какое наименьшее количество вопросов вида «Загаданное тобой число больше числа X?», подразумевающих ответы «Да» или «Нет», мальчик гарантированно сможет отгадать число девочки?

Примеры:
6
3

2
1

@Royal_X · 10.12.2023, 15:36

Python
1
2
from math import ceil, log2
print(ceil(log2(int(input()))))

@IlyaTop · 10.12.2023, 15:53 **[ТС]**

Royal_X, ошибка на 14 тесте, как и у меня

@Royal_X · 10.12.2023, 16:00

IlyaTop, а как ты писал?

@IlyaTop · 10.12.2023, 16:05 **[ТС]**

Royal_X, этот код доходит до 19:

Python
1
2
3
4
5
6
7
q = int(input())
from math import floor
t = 0
while q != 1:
    q = floor((q + 1) / 2)
    t += 1
print(t)

@thyrex · 10.12.2023, 16:42

Python
1
2
3
4
5
6
q = int(input())
t = 0
while q != 1:
    q = (q + 1) // 2
    t += 1
print(t)

Добавлено через 1 минуту
Вообще, глядя на все созданные Вами темы, наблюдаются непонятные хаотичные прыжки с одной тематики на другую

@Royal_X · 10.12.2023, 17:39

thyrex, наши коды работают аналогично:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from math import ceil, log2
 
def f1(n):
    return ceil(log2(n))
 
def f2(q):
    t = 0
    while q != 1:
        q = (q + 1) // 2
        t += 1
    return t
 
a = []
b = []
for i in range(1,10**6):
    a.append(f1(i))
    b.append(f2(i))
    
print(a == b)

Получаю True

Не знаю почему, но ТС говорит, что мой не проходит какой-то тест. Касательно вашего, он пока не высказался. Но, как по мне, у нас у обоих правильные коды.

@IlyaTop · 10.12.2023, 17:53 **[ТС]**

thyrex, все правильно, спасибо

Добавлено через 46 секунд
Royal_X, лимит по памяти

@Royal_X · 10.12.2023, 17:57

IlyaTop, так в условии нужно писать о лимитах и в том числе о максимальном N. Уверен, что в оригинальном условии об этом сказано.

@IlyaTop · 10.12.2023, 18:05 **[ТС]**

Royal_X, 1 сек 16 МБ, N <= 5 * 10¹⁸

@Royal_X · 10.12.2023, 18:07

IlyaTop, видишь ли, код с логарифмом в разы быстрее цикла. Но на больших числах, наверное, жрет много памяти. Хотя, я не уверен. Нужно считать. Я пишу с телефона, нет возможности проверять.

@thyrex · 10.12.2023, 18:16

Royal_X, я не сторонник гнаться за временем, если решение и так укладывается в лимит. Да и глупо использовать в бинарном поиске обычное, а не целочисленное деление. Быть может, в каких-то случаях оно и нужно, но подозреваю, что таких случаев намного меньше, если они есть.

@Royal_X · 10.12.2023, 18:18

thyrex, а я, наоборот, предпочитаю вычислять по формуле, если это возможно

@thyrex · 10.12.2023, 19:34

Royal_X, а у меня разве не формула? Задачу роднит с бинарным поиском только сокращение отрезка в 2 раза. Задачи на настоящий бинарный поиск на acmp расположены в разделе Курсы.

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@IlyaTop 2 / 2 / 0 Регистрация: 02.12.2023 Сообщений: 80

	Python бинарный поиск 10.12.2023, 15:05. Показов 1001. Ответов 13 Метки python, задача (Все метки) Девочка загадала число от 1 до N. За какое наименьшее количество вопросов вида «Загаданное тобой число больше числа X?», подразумевающих ответы «Да» или «Нет», мальчик гарантированно сможет отгадать число девочки? Примеры: 6 3 2 1 0

@IlyaTop 2 / 2 / 0 Регистрация: 02.12.2023 Сообщений: 80
	10.12.2023, 15:53 [ТС]
	Royal_X, ошибка на 14 тесте, как и у меня 0

@Royal_X 6234 / 2943 / 1047 Регистрация: 01.06.2021 Сообщений: 10,954
	10.12.2023, 16:00
	IlyaTop, а как ты писал? 1

@IlyaTop 2 / 2 / 0 Регистрация: 02.12.2023 Сообщений: 80
	10.12.2023, 17:53 [ТС]
	thyrex, все правильно, спасибо Добавлено через 46 секунд Royal_X, лимит по памяти 0

@Royal_X 6234 / 2943 / 1047 Регистрация: 01.06.2021 Сообщений: 10,954
	10.12.2023, 17:57
	IlyaTop, так в условии нужно писать о лимитах и в том числе о максимальном N. Уверен, что в оригинальном условии об этом сказано. 1

@IlyaTop 2 / 2 / 0 Регистрация: 02.12.2023 Сообщений: 80
	10.12.2023, 18:05 [ТС]
	Royal_X, 1 сек 16 МБ, N <= 5 * 10¹⁸ 0

@Royal_X 6234 / 2943 / 1047 Регистрация: 01.06.2021 Сообщений: 10,954
	10.12.2023, 18:07
	IlyaTop, видишь ли, код с логарифмом в разы быстрее цикла. Но на больших числах, наверное, жрет много памяти. Хотя, я не уверен. Нужно считать. Я пишу с телефона, нет возможности проверять. 1

@thyrex 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	10.12.2023, 18:16
	Royal_X, я не сторонник гнаться за временем, если решение и так укладывается в лимит. Да и глупо использовать в бинарном поиске обычное, а не целочисленное деление. Быть может, в каких-то случаях оно и нужно, но подозреваю, что таких случаев намного меньше, если они есть. 1

@Royal_X 6234 / 2943 / 1047 Регистрация: 01.06.2021 Сообщений: 10,954
	10.12.2023, 18:18
	thyrex, а я, наоборот, предпочитаю вычислять по формуле, если это возможно 1

@thyrex 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	10.12.2023, 19:34
	Royal_X, а у меня разве не формула? Задачу роднит с бинарным поиском только сокращение отрезка в 2 раза. Задачи на настоящий бинарный поиск на acmp расположены в разделе Курсы. 0

Python бинарный поиск

Решение