Fixed point

2.17 in DPV: 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