Advertisement
zhongnaomi

Linear search and binary search timeit

Feb 15th, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.51 KB | None | 0 0
  1. from timeit import timeit
  2. from random import randint
  3.  
  4. list_to_search = [i for i in range(1000000)]
  5.  
  6. #######################################################################
  7. # COPY AND PASTE YOUR linear_search AND binary_search functions below #
  8.  
  9. def binary_search(sorted_list,value):
  10.    
  11.    
  12.    
  13.     left =0
  14.     right = len(sorted_list)-1
  15.     while left <= right :
  16.         mid = int((left + right)/2)
  17.        
  18.        
  19.         if sorted_list[mid]<value:
  20.             left = mid+1
  21.            
  22.         elif sorted_list[mid]>value:
  23.             right = mid-1
  24.            
  25.         else:
  26.             return mid
  27.     return -1
  28.  
  29. def linear_search(arr, x):
  30.     n = len(arr)
  31.     for i in range (0, n):
  32.         if (arr[i] == x):
  33.             return i
  34.     return -1
  35.  
  36.  
  37.  
  38.  
  39. #######################################################################
  40.  
  41. ls = lambda: linear_search(list_to_search, randint(0,1000000))
  42. bs = lambda: binary_search(list_to_search, randint(0,1000000))
  43. result = linear_search(list_to_search, randint(0,1000000))
  44. result2 = binary_search(list_to_search, randint(0,1000000))
  45. if(result == -1):
  46.     print("Element is not present in array")
  47. else:
  48.     print("LElement is present at index", result)
  49. if(result2 == -1):
  50.     print("Element is not present in list")
  51. else:
  52.     print("bElement is present at index", result2)
  53. #time the functions for 100 runs each
  54. print("Linear search took:")
  55. print(timeit(ls, number = 100))
  56.  
  57. print("Binary search took:")
  58. print(timeit(bs, number = 100))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement