CODEWITHSUNDEEP
pythonnumbersbinary-search-treebinary-search
boolean.is.null
boolean.is.null

Reputation: 881

Binary search to find the highest possible value in Python

I have a very large number (20 digits), which I need to find. So in a range between 0 and 99999999999999999999.

I can perform a check if the number is larger or smaller than the guessed number, so for example:

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

However, how the function is_smaller works is unknown, but the value for a number is constant.

Could this be solved with a binary search - I'm not quite sure how I can implement this as I only ever know If the number is smaller/larger. Most implementations of the binary search I've come across, use it to find a given number in an array, which doesn't work for me as the number is unknown.

How could I use binary search in this scenario, or would another method be better suited?

The goal is to find the highest possible value, that still returns True for is_smaller.

edit: I do not have a way of telling if the number is bigger, so I have no is_bigger function. So in a smaller range (e.g. 0 to 10), if the number of interest is 6, the function I have would return:

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

I have to admit the functions name in the question was very poorly chosen.

Upvotes: 0

Views: 714

Answers (2)

Matt Morgan
Matt Morgan

Reputation: 21

If something is neither bigger nor smaller than the number you're looking for, it's the number you're looking for.

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

Now you can use standard binary search; just replace conditionals that look like

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

With

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

Respectively. If you want a <= or >= operator for your binary search, you can construct it yourself from these building blocks.

Upvotes: 2

Daniel
Daniel

Reputation: 42748

Binary search splits a range from lower_boundary .. higher_boundary to the range lower_boundary .. (lower_boundary + higher_boundary) // 2 or (lower_boundary + higher_boundary) // 2 + 1 .. lower_boundary depending on the outcome of your is_smaller function.

Upvotes: 0

Related Questions