Preview:
#method 1
def evaluate(n, l, r, m, list_a):
    if list_a[m] > n:
        r = m
        m = (l+r) // 2
    elif list_a[m] < n:
        l = m+1
        m = (l+r) // 2
    elif list_a[m] == n:
        return "found"
    return (l, r, m)
    
def binary_search(list_a, n):
    l, r = 0, len(list_a) - 1
    m = (l+r) // 2
    
    while True:
        try:
            l, r, m = evaluate(n, l, r, m, list_a)
      
        except Exception:
            break
  
    return m
    

#method 2
def recursive_binary_search(list_a, target, l = None, r = None):
    if list_a == []:
        return None
        
    if l == None and r == None:
        l = 0
        r = len(list_a) - 1
        
    mid = (l + r) // 2
    
    if list_a[mid] == target:
        return mid
    elif target < list_a[mid]:
        return recursive_binary_search(list_a, target, l, mid - 1)
    elif target > list_a[mid]:
        return recursive_binary_search(list_a, target, mid + 1, r)
        
def naive_search(list_a, target):
    for i in list_a:
        if i == target:
            return target
    return None

#test
from random import*
from time import*

sorted_list = set()
length = 1000

while len(sorted_list) < length:
    sorted_list.add(randint(-8 * length, 8* length))

sorted_list = sorted(list(sorted_list))

start = time()
for target in sorted_list:
    naive_search(sorted_list, target)
end = time()
print("Naive Search:", (end - start) / length)

start = time()
for target in sorted_list:
    binary_search(sorted_list, target)
end = time()
print("Binary Search:", (end - start) / length)
    
start = time()
for target in sorted_list:
    recursive_binary_search(sorted_list, target)
end = time()
print("Recursive Binary Search:", (end - start) / length)

   
downloadDownload PNG downloadDownload JPEG downloadDownload SVG

Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!

Click to optimize width for Twitter