take in a random list and a search number
iterate along each index of that list
if the query is equal to the item at that index:
- append the index of that item to a new list
if the output list has items in it:
- output the list
otherwise:
- output item not found

This search is pretty inefficient, since it has to look at every item in the list no matter what. I tried to at least get it to only search until the query was greater than the current item, but my ability to make a while loop that works is currently limited, it seems



In [40]:

    
def list_search(query, input_list):
    output_list=[]
    for index in range(len(input_list)):
        if input_list[index]==query:
            output_list.append(index)
    if output_list:
        return output_list
    else:
        return 'item not found'



In [37]:

    
from random import randint
sorted_list_10=sorted([randint(0,999) for i in range(10)])
sorted_list_100=sorted([randint(0,999) for i in range(100)])
sorted_list_1000=sorted([randint(0,999) for i in range(1000)])



In [74]:

    
%time list_search(35, sorted_list_1000)









    



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






    Out[74]:





[20, 21, 22]



In [75]:

    
%time [i for i, x in enumerate(sorted_list_1000) if x==35]









    



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






    Out[75]:





[20, 21, 22]

That was for testing. Interesting that the super pythonic list comprehension is just a little bit faster, but I think it works in basically the same way.

Here is the same thing but using my code from assignment 1:



In [62]:

    
def list_sort(input_list):
    output_list=[]
    for input_item in input_list:
        if not output_list:
            output_list.append(input_item)
        else:
            index=0
            for a in range(len(output_list)):
                if output_list[index]<input_item:
                    index+=1
            if index==len(output_list):
                output_list.append(input_item)
            else:
                first_half=output_list[:index]
                first_half.append(input_item)
                last_half=output_list[index:]
                output_list=first_half+last_half
    return output_list



In [63]:

    
def random_list_maker(list_len):
    from random import randint
    return_list=[]
    for i in range(list_len):
        return_list.append(randint(0,999))
    return return_list



In [81]:

    
# this will actually generate a new list of 1000 random numbers, sort them, and then search them for
# the number specified, returning the indices of any instances of that number
# this whole operation is pretty slow
%time list_search(20, list_sort(random_list_maker(1000)))









    



CPU times: user 48 ms, sys: 4 ms, total: 52 ms
Wall time: 85.7 ms






    Out[81]:





[19]



In [102]:

    
# i'm pretty sure this is the same operation as above but mashed into one list comprehendion, 
# using built in functions and libraries. it is a lot faster.
%time [i for i, x in enumerate(sorted([randint(0,999) for i in range(1000)])) if x==20]









    



CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 2.16 ms






    Out[102]:





[18]



In [ ]: