Input: a sorted list and a search term Operation: find the element in the list Output: the location of the item in the list or indicate if it's not there

``````

In [2]:

import random

``````
``````

In [10]:

def find_value_index(sorted_list, search_term):

def check_repeats():
try:
while search_term == sorted_list[other_index + 1]:
other_index += 1
except:
while search_term == sorted_list[other_index - 1]:
other_index -= 1

start_index = 0
end_index = len(sorted_list) - 1
while end_index - start_index > 1:
middle_index = int((end_index - start_index) / 2 + start_index)
if search_term == sorted_list[start_index]:
check_repeats()
elif search_term == sorted_list[end_index]:
check_repeats()
elif search_term == sorted_list[middle_index]:
check_repeats()
elif search_term < sorted_list[middle_index]:
end_index = middle_index
else:
start_index = middle_index

``````
``````

In [17]:

list10 = []
for x in range(10):
list10.append(random.randrange(100))
list10.sort()

``````
``````

In [18]:

list100 = []
for x in range(100):
list100.append(random.randrange(100))
list100.sort()

``````
``````

In [19]:

list1000 = []
for x in range(1000):
list1000.append(random.randrange(100))
list1000.sort()

``````
``````

In [20]:

%time find_value_index(list10, 50)

``````
``````

CPU times: user 16 µs, sys: 0 ns, total: 16 µs
Wall time: 21 µs

Out[20]:

[3]

``````
``````

In [21]:

%time find_value_index(list100, 50)

``````
``````

CPU times: user 16 µs, sys: 1 µs, total: 17 µs
Wall time: 21.9 µs

Out[21]:

[49]

``````
``````

In [22]:

%time find_value_index(list1000, 50)

``````
``````

CPU times: user 35 µs, sys: 1 µs, total: 36 µs
Wall time: 39.8 µs

Out[22]:

[514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525]

``````
``````

In [ ]:

``````