Advertisement
JAS_Software

Linear Binary Comparison

May 18th, 2021
47
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from time import time
  2. from random import randint
  3.  
  4.  
  5. def generateOrderedList(numberOfElements):
  6.     elements = []
  7.     for i in range(0,numberOfElements):
  8.         elements.append(i)
  9.     return elements
  10.  
  11.  
  12. def generateRandomList(numberOfElements):
  13.     elements = []
  14.     for i in range(0,numberOfElements):
  15.         value = randint(1,40)
  16.         elements.append(value)
  17.     return elements
  18.  
  19. def getItem():
  20.     return input('Enter Item to search for: ')
  21.  
  22.  
  23. def binarySearch(elements,searchTerm):
  24.     lower = 0
  25.     upper = len(elements)
  26.     while lower <= upper:
  27.         middle = calculateMiddle(lower,upper)
  28.         if elements[middle] > searchTerm:
  29.             upper = middle -1
  30.         elif elements[middle] < searchTerm:
  31.             lower = middle + 1
  32.         else:
  33.             return middle
  34.     return -1
  35.  
  36. def linearSearch(elements,searchTerm):
  37.     #loop through list until found or end of list is reached
  38.     pos = 0
  39.     while pos < len(elements):
  40.         if elements[pos] == searchTerm:
  41.             return pos
  42.         pos +=1
  43.     return -1
  44.  
  45.  
  46. def calculateMiddle(lower,upper):
  47.     #calculate the middle value between the upper and lower limits of the current sublist
  48.     return int((upper + lower) / 2)
  49.  
  50. elements = generateOrderedList(10000000)
  51. searchTerm = float(getItem())
  52. startTime = time()
  53.  
  54.  
  55. print('-----')
  56. print('Binary Search')
  57. location = binarySearch(elements,searchTerm)
  58. print("Found:" + str(float(time() - startTime)))
  59.  
  60. startTime = time()
  61. print('-----')
  62. print('Linear Search')
  63. location = linearSearch(elements,searchTerm)
  64. print("Found:" + str(float(time() - startTime)))
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement