Assignment 2

Implement the search algorithm you came up with in pseudocode with Python

Test the search algorithm with a list of 10,100,1000 random numbers (sorted with your sorting algorithm) and compare

the result using the %time to time your code and submit your results in code comments

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

    
import random



In [5]:

    
#We can do this in two different ways.
#I will do both and see the time difference.
#With the ---linear search--- we can check ALL values in order until we find the one we want 
#With the ---binary search--- we check for the value in the middle of the list, eliminating the
#half of the list that are smaller or bigger than the number we are looking for.

Sorting function



In [6]:

    
def sorting_function(my_list):
    for index in range(1,len(my_list)): 
        index_number= my_list[index] 
        index_to_the_left= index - 1 
        while index_to_the_left >=0:
            if index_number < my_list[index_to_the_left]:
                my_list[index_to_the_left+1] = my_list[index_to_the_left] 
                my_list[index_to_the_left] = index_number 
                index_to_the_left = index_to_the_left -1
            else:
                break
    return my_list



In [7]:

    
list_of_10= random.sample(range(1,11),10)
sorting_function(list_of_10)









    Out[7]:





[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Using linear search with enumerate function



In [8]:

    
def linear_search_function(list_of_items, item_we_want):
    for index_number, item in enumerate(list_of_items):
        if item == item_we_want:
            return index_number

    raise ValueError("%s was not found in the list." % desired_item)



In [9]:

    
% time linear_search_function(list_of_10, 6) #it works!

# CPU times: user 7 µs, sys: 1e+03 ns, total: 8 µs
# Wall time: 20 µs









    



CPU times: user 11 µs, sys: 1 µs, total: 12 µs
Wall time: 16.9 µs






    Out[9]:





5

Using Binary search



In [27]:

    
list_of_twenty= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]



In [32]:

    
def binary_search_function(list_of_items, value):
    start= 0
    end= len(list_of_items)-1
    while end - start >1:
      
        if value == list_of_items[start]:
            return start
        
        if value == list_of_items[end]:
            return end
        
        mid = int((start + end) // 2)
        
        if value == int(list_of_items[mid]):
            return mid
        
        elif value > list_of_items[mid]:
            start = mid

        else:
            end = mid



In [33]:

    
binary_search_function(list_of_twenty, 9)









    Out[33]:





8



In [ ]: