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