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

In computer science, a search algorithm is an algorithm that retrieves information stored within some data structure. Data structures can include linked lists, arrays, search trees, hash tables, or various other storage methods. The appropriate search algorithm often depends on the data structure being searched


In [ ]:
#search algorithm
#input: a sorted list and a search term
#operation: find the element in that list
#output: location of the item in the list or indicate if it's not there
# the binary search will start by examing in the middle term

In [7]:
def binarysearch(sorted_list, item):
    if len(sorted_list)==0:
        return False
    else:
        start=0
        end=len(sorted_list)-1
        midpoint=(start+end)/2
        midpoint = int(midpoint)
        print(midpoint)
        if sorted_list[midpoint]==item:
            return True
        else:
            if item < sorted_list[midpoint]:
                end=midpoint-1
            else:
                start=midpoint+1

In [8]:
sorted_list=[0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarysearch(sorted_list,13))


4
True

In [14]:
import random

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

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

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

In [19]:
%time binarysearch(list10, 5)


4
CPU times: user 45 µs, sys: 0 ns, total: 45 µs
Wall time: 50.1 µs

In [20]:
%time binarysearch(list100, 50)


49
CPU times: user 54 µs, sys: 11 µs, total: 65 µs
Wall time: 69.9 µs

In [21]:
%time binarysearch(list1000, 500)


499
CPU times: user 35 µs, sys: 0 ns, total: 35 µs
Wall time: 37.9 µs

In [ ]: