Search Algorithm


In [2]:
def sort_list(listed):
    
    # for each index number in the list starting at 1: 
    for i in range(1,len(listed)):
        
        # set the current value equal to the value at index, i: 
        currentvalue = listed[i]
#         print('current value:', currentvalue)
        
        # set position to index of the current value
        position = i
#         print('position:', position)
    
        # while the index number is greater than zero and the value before the current value 
        # is greater than the current value:
        while position>0 and listed[position-1]>currentvalue:
#                 print('Index position', position, 'is greater than 0')
#                 print('The value at index position', position, 'is', listed[position])
#                 print ('And the value at index position', position-1, 'is', listed[position-1], 'which is greater than', currentvalue)
#                 print('We change the value of', listed[position], 'to', listed[position-1])
                listed[position]=listed[position-1]
#                 print('We change the value of the variable storing index position from', position, 'to', position-1)
                position = position-1

    
        listed[position]=currentvalue
#         print('Index position equals 0, so we exit the loop')
#         print('And we set the value at index position', position, "to", currentvalue)

In [3]:
def search_list(listed, search_item):
        # set start to index position zero
        start = 0
        # set end to last index position: 
        end = len(alist)-1
        found = False
        
        # while start index is less than or equal to end index and found is False: 
        while start<=end and not found:
            # set middle to half the length of the list
            middle = int((start + end)//2)
            # if the value at the middle index position equals the search item: 
            if listed[middle] == search_item:
                # set found equal to True
                found = True
            # if the value at the middle index position does not equal the search item: 
            else:
                # if the search item is less than the value at the middle index: 
                if search_item < listed[middle]:
                    # then set end to index position middle-1
                    end = middle-1
                # if the search item is greater than the value at the middle index:     
                else:
                    # then set start to index position middle+1
                    start = middle+1
        # return found value, search item value, index position
        return found, search_item, middle

In [7]:
import random

lengths=[10,100,1000]
for x in lengths:  
    alist = random.sample(range(x), x)
    sort_list(alist)
    %time search_list(alist, random.choice(alist))

# for a list length 10: 
# CPU times: user 13 µs, sys: 1 µs, total: 14 µs
# Wall time: 14.8 µs
    
# for a list length 100: 
# CPU times: user 15 µs, sys: 0 ns, total: 15 µs
# Wall time: 18.1 µs
    
# for a list length 1000: 
# CPU times: user 17 µs, sys: 0 ns, total: 17 µs
# Wall time: 20 µs


CPU times: user 11 µs, sys: 1 µs, total: 12 µs
Wall time: 13.8 µs
CPU times: user 20 µs, sys: 1 µs, total: 21 µs
Wall time: 26 µs
CPU times: user 21 µs, sys: 0 ns, total: 21 µs
Wall time: 25 µs

In [ ]: