Fixed point

In [31]:

    

from typing import List

import numpy as np


    

In [40]:

    

def find_index_equals_val(lst: List[int], b: int, e: int, depth: int=0) -> bool:
    assert sorted(lst) == lst
    assert len(set(lst)) == len(lst)
    
    m = b + (e - b) // 2
    last = e - b == 1
    
    if m == lst[m]:
        print(f'depth: {depth}, log2(n): {np.log2(len(lst))}')
        return True
    else:
        if lst[m] < m:
            # go right
            if last:
                print(f'depth: {depth}, log2(n): {np.log2(len(lst))}')
                return lst[e] == e
            return find_index_equals_val(lst, m, e, depth + 1)
        else:
            # go left
            if last:
                print(f'depth: {depth}, log2(n): {np.log2(len(lst))}')
                return lst[b] == b
            return find_index_equals_val(lst, b, m, depth + 1)


    

In [41]:

    

find_index_equals_val([1, 2, 3], 0, 2) == False


    

    




depth: 1, log2(n): 1.584962500721156






    
Out[41]:





True

In [42]:

    

find_index_equals_val([0, 1, 3], 0, 2) == True


    

    




depth: 0, log2(n): 1.584962500721156






    
Out[42]:





True

In [43]:

    

find_index_equals_val([-1, 1, 2, 3], 0, 3) == True


    

    




depth: 0, log2(n): 2.0






    
Out[43]:





True

In [44]:

    

find_index_equals_val([-1, 0, 2, 3], 0, 3) == True


    

    




depth: 1, log2(n): 2.0






    
Out[44]:





True

In [48]:

    

len(list(range(-1, 10)) + list(range(100, 200)))


    

    
Out[48]:





111

In [50]:

    

find_index_equals_val(list(range(-1, 10)) + list(range(100, 200)), 0, 110) == False


    

    




depth: 7, log2(n): 6.794415866350106






    
Out[50]:





True

In [59]:

    

find_index_equals_val(list(range(-1, 10)) + [11] + list(range(1000, 2000)), 0, 1010) == True


    

    




depth: 7, log2(n): 9.98299357469431






    
Out[59]:





True