notebook.community

Edit and run

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):
    answer = []
    
    def check_repeats():
            other_index = answer[0]
            try:
                while search_term == sorted_list[other_index + 1]:
                    answer.append(other_index + 1)
                    other_index += 1
            except:
                other_index = answer[0]
                while search_term == sorted_list[other_index - 1]:
                    answer.append(other_index - 1)
                    other_index -= 1
                return answer

    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]:
            answer.append(start_index)
            check_repeats()
            return answer
        elif search_term == sorted_list[end_index]:
            answer.append(end_index)
            check_repeats()
            return answer
        elif search_term == sorted_list[middle_index]:
            answer.append(middle_index)
            check_repeats()
            return answer
        elif search_term < sorted_list[middle_index]:
            end_index = middle_index
        else:
            start_index = middle_index
    return 'Value not found'



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 [ ]: