# Binary Search

Wed Nov 30 2022 12:02:58 GMT+0000 (UTC)

Saved by @Parker_kim #python

```#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 = 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)

```
content_copyCOPY

This code explores the concept of binary search and demonstrates the efficiency of binary search by comparing different algorithms!