Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from timeit import timeit
- from random import randint
- list_to_search = [i for i in range(1000000)]
- #######################################################################
- # COPY AND PASTE YOUR linear_search AND binary_search functions below #
- def binary_search(sorted_list,value):
- left =0
- right = len(sorted_list)-1
- while left <= right :
- mid = int((left + right)/2)
- if sorted_list[mid]<value:
- left = mid+1
- elif sorted_list[mid]>value:
- right = mid-1
- else:
- return mid
- return -1
- def linear_search(arr, x):
- n = len(arr)
- for i in range (0, n):
- if (arr[i] == x):
- return i
- return -1
- #######################################################################
- ls = lambda: linear_search(list_to_search, randint(0,1000000))
- bs = lambda: binary_search(list_to_search, randint(0,1000000))
- result = linear_search(list_to_search, randint(0,1000000))
- result2 = binary_search(list_to_search, randint(0,1000000))
- if(result == -1):
- print("Element is not present in array")
- else:
- print("LElement is present at index", result)
- if(result2 == -1):
- print("Element is not present in list")
- else:
- print("bElement is present at index", result2)
- #time the functions for 100 runs each
- print("Linear search took:")
- print(timeit(ls, number = 100))
- print("Binary search took:")
- print(timeit(bs, number = 100))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement