In [94]:

    

# This code works for positive integers and assumes the list is already sorted
def binary_search(list, value):
    high = len(list) - 1;
    low = 0;
    #print("The length of the list is", len(list))
        #counter is used to track the index point 
        #that the binary_search is looking at
    counter = int((high+low)/2) # start by looking at the middle 

        #if the list is empty do not proceed!
    if len(list) == 0:
        return 0
        
    while low < high: # and counter <= high
        #print("counter is", counter)
        #print(list[counter])
        #print(value)
        if list[counter] == value:
            return print("Value of", value, "was found at the index", counter)
        elif low < value < list[counter]:
            high = list[counter - 1]
            counter = counter -1 
        elif value == 0:
            if list[0] == 0:
                 return print("Value of", value, "was found at the index 0")
            else:
                return print("Unfortunately", value, "was not found in this list.")
       
        else: 
            low = list[counter]
            counter = counter + 1
    return print("Unfortunately", value, "was not found in this list.")


    

In [95]:

    

binary_search([1,2,3,4], 0)


    

    




Unfortunately 0 was not found in this list.

In [96]:

    

def sort(list):
    times = len(list) - 1
    # create a new empty list to add sorted values 
    sorted = []


    while times + 1> 0:
        min = list[0]
        for item in list:
             if item < min:
                    min = item
        # after finding the smallest element, append it to the new sorted list
        sorted.append(min)
        
        #remove the smallest element from the original list 
        list.remove(min)
        
        #incremenet the number of times, in order to get closer to the condition
        # that will halt this while loops 
        times = times - 1
    
    return sorted


    

In [97]:

    

from random import randint

def random_num_gen(x):
    random_list = [] 
    count = 0 
    while count < x:
        random_list.append(randint(0,100))
        count = count + 1
    return random_list

ten_sample = random_num_gen(10)
hundred_sample = random_num_gen(100)
thousand_sample = random_num_gen(1000)


    

In [98]:

    

thousand_sample = sort(thousand_sample)
ten_sample = sort(ten_sample)
hundred_sample = sort(hundred_sample)


    

In [99]:

    

%time binary_search(thousand_sample, 35)


    

    




Value of 35 was found at the index 340
CPU times: user 133 µs, sys: 1 µs, total: 134 µs
Wall time: 138 µs

In [ ]:

    

print(hundred_sample)


    

In [100]:

    

%time binary_search(hundred_sample, 31)


    

    




Unfortunately 31 was not found in this list.
CPU times: user 63 µs, sys: 0 ns, total: 63 µs
Wall time: 67.9 µs

In [101]:

    

%time binary_search(hundred_sample, 45)


    

    




Value of 45 was found at the index 49
CPU times: user 66 µs, sys: 0 ns, total: 66 µs
Wall time: 70.8 µs

In [102]:

    

print(ten_sample)


    

    




[16, 23, 38, 43, 69, 73, 76, 79, 91, 100]

In [103]:

    

type(hundred_sample)


    

    
Out[103]:





list

In [104]:

    

%time binary_search(ten_sample, 99)


    

    




Unfortunately 99 was not found in this list.
CPU times: user 56 µs, sys: 1 µs, total: 57 µs
Wall time: 61 µs

In [105]:

    

print(ten_sample)


    

    




[16, 23, 38, 43, 69, 73, 76, 79, 91, 100]

In [107]:

    

%time binary_search(hundred_sample, 15)


    

    




Value of 15 was found at the index 10
CPU times: user 73 µs, sys: 1 µs, total: 74 µs
Wall time: 77 µs

In [108]:

    

%time binary_search(hundred_sample, 3)


    

    




Unfortunately 3 was not found in this list.
CPU times: user 141 µs, sys: 1 µs, total: 142 µs
Wall time: 150 µs

In [109]:

    

%time binary_search(hundred_sample, 343)


    

    




---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-109-10ce12396802> in <module>()
----> 1 get_ipython().magic('time binary_search(hundred_sample, 343)')

/Users/Monica/.virtualenvs/dataanalysis/lib/python3.5/site-packages/IPython/core/interactiveshell.py in magic(self, arg_s)
   2161         magic_name, _, magic_arg_s = arg_s.partition(' ')
   2162         magic_name = magic_name.lstrip(prefilter.ESC_MAGIC)
-> 2163         return self.run_line_magic(magic_name, magic_arg_s)
   2164 
   2165     #-------------------------------------------------------------------------

/Users/Monica/.virtualenvs/dataanalysis/lib/python3.5/site-packages/IPython/core/interactiveshell.py in run_line_magic(self, magic_name, line)
   2082                 kwargs['local_ns'] = sys._getframe(stack_depth).f_locals
   2083             with self.builtin_trap:
-> 2084                 result = fn(*args,**kwargs)
   2085             return result
   2086 

<decorator-gen-60> in time(self, line, cell, local_ns)

/Users/Monica/.virtualenvs/dataanalysis/lib/python3.5/site-packages/IPython/core/magic.py in <lambda>(f, *a, **k)
    191     # but it's overkill for just that one bit of state.
    192     def magic_deco(arg):
--> 193         call = lambda f, *a, **k: f(*a, **k)
    194 
    195         if callable(arg):

/Users/Monica/.virtualenvs/dataanalysis/lib/python3.5/site-packages/IPython/core/magics/execution.py in time(self, line, cell, local_ns)
   1171         if mode=='eval':
   1172             st = clock2()
-> 1173             out = eval(code, glob, local_ns)
   1174             end = clock2()
   1175         else:

<timed eval> in <module>()

<ipython-input-94-d22818d25130> in binary_search(list, value)
     16         #print(list[counter])
     17         #print(value)
---> 18         if list[counter] == value:
     19             return print("Value of", value, "was found at the index", counter)
     20         elif low < value < list[counter]:

IndexError: list index out of range

In [110]:

    

%time binary_search(ten_sample, 32)


    

    




Unfortunately 32 was not found in this list.
CPU times: user 95 µs, sys: 1 µs, total: 96 µs
Wall time: 103 µs

In [ ]: