Двоичный поиск, чтобы найти максимально возможное значение в Python

Question

У меня очень большое число (20 цифр), которое мне нужно найти.Таким образом, в диапазоне от 0 до 99999999999999999999.

Я могу выполнить проверку, если число больше или меньше, чем предполагаемое число, например:

is_smaller(12341234123412341234)
# True
is_smaller(98769876987698769876)
# False

Однако, как функцияis_smaller работает неизвестно, но значение для числа является постоянным.

Может ли это быть решено с помощью бинарного поиска - я не совсем уверен, как я могу реализовать это, поскольку я только когда-либо знаю, если числоменьше / большеБольшинство реализаций бинарного поиска , с которыми я сталкивался , используют его для поиска заданного числа в массиве, что не работает для меня, поскольку число неизвестно.

Как могЯ использую бинарный поиск в этом сценарии, или другой метод лучше подходит?

Цель состоит в том, чтобы найти максимально возможное значение, которое все еще возвращает True для is_smaller.

---

edit: У меня нет способа узнать, больше ли число, поэтому у меня нет функции is_bigger.Таким образом, в меньшем диапазоне (например, от 0 до 10), если интересующее число равно 6 , функция, которую я имею, вернет:

[...]
is_smaller(4)
# True
is_smaller(5)
# True
is_smaller(6)
# True
is_smaller(7)
# False
is_smaller(8)
# False

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

Answer 1

Двоичный поиск разбивает диапазон от lower_boundary .. higher_boundary до диапазона lower_boundary .. (lower_boundary + higher_boundary) // 2 или (lower_boundary + higher_boundary) // 2 + 1 .. lower_boundary в зависимости от результата вашей функции is_smaller.

Answer 2

Если что-то ни больше, ни меньше числа, которое вы ищете, это число, которое вы ищете.

def is_answer(n):
    return not is_smaller(n) and not is_larger(n)

Теперь вы можете использовать стандартный бинарный поиск; просто замените условия, которые выглядят как

if x == search_term:
if x < search_term:
if x > search_term:

С

if is_answer(x):
if is_smaller(x):
if is_larger(x):

соответственно. Если вам нужен оператор <= или >= для бинарного поиска, вы можете создать его самостоятельно из этих строительных блоков.