0

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.

boolean.is.null
  • 831
  • 2
  • 12
  • 19

2 Answers2

2

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.

Idan Str
  • 614
  • 1
  • 11
  • 33
Matt Morgan
  • 21
  • 2
  • Thank you very much for the feedback! I've edited the question as I have no way of telling if a number is bigger than the number of interest. It is either bigger, or the number itself (see the code example in the edit). – boolean.is.null May 14 '18 at 16:43
0

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.

Daniel
  • 42,087
  • 4
  • 55
  • 81