# 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

``````