finding $x$ in an infinite array

In [2]:

    

import numpy as np


    

In [158]:

    

# let's pretend that n is not known to us
# n is the number of elements that are populated
# the rest are infinity
n = int(2e10)
n = 10


    

In [159]:

    

# we only have access to this function
# which checks if the value at that index is infinity or not
def val_inf(i):
    return True if i >= n else False


    

In [167]:

    

def find_n(b: int, e: int, depth: int=0) -> int:
    """
    b: beginning of the range
    e: end of the range
    depth: keep track of recursion depth
    """
    
    # catch the case of n == 0
    if val_inf(b):
        return b
    
    # is the value of e
    inf_e = val_inf(e)
    
    if inf_e:
        m = (e - b) // 2 + b
        inf_m = val_inf(m)
        
        # eureka
        if not inf_m and e - m == 1:
            print(f'depth: {depth}, log2(n): {np.log2(n)}')
            return e
        
        if inf_m:
            return find_n(b, m, depth + 1)
        else:
            return find_n(m, e, depth + 1)
    else:
        # expand the range
        return find_n(e, e ** 2, depth + 1)


    

In [168]:

    

find_n(0, 100)


    

    




depth: 6, log2(n): 3.321928094887362






    
Out[168]:





10