#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)
Preview:
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