#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)
Comments