# Binary Searches

May 18th, 2021
68
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from random import randint
2.
3. def generateOrderedList(x):
4.     elements = list(range(1,x))
5.     return elements
6.
7. def generateRandomList(numberOfElements):
8.     #create list of random numbers
9.     elements = []
10.     for i in range(0,numberOfElements):
11.         value = randint(1,40)
12.         elements.append(value)
13.     return elements
14.
15. def getItem():
16.     return input('Enter Item to search for: ')
17.
18. def binarySearch(elements,searchTerm):
19.     lower = 0
20.     upper = len(elements)
21.     while lower <= upper:
22.         middle = calculateMiddle(lower,upper)
23.         #print(lower,middle,upper,elements[middle])
24.         if elements[middle] > searchTerm:
25.             upper = middle -1
26.             #print(elements[lower:upper])
27.         elif elements[middle] < searchTerm:
28.             lower = middle + 1
29.             #print(elements[lower:upper])
30.         else:
31.             return middle
32.     return -1
33.
34.
35.
36. def binarySearchSame(elements,element,direction):
37.     lower = 0
38.     upper = len(elements) - 1
39.     while lower <= upper:
40.         middle = calculateMiddle(lower,upper)
41.         #print(lower,middle,upper,elements[middle])
42.         if elements[middle] > element:
43.             upper = middle -1
44.             #print(elements[lower:upper+1])
45.         elif elements[middle] < element:
46.             lower = middle + 1
47.             #print(elements[lower:upper+1])
48.         else:
49.             same = True
50.             prevMiddle = middle
51.             while same and middle >= 0 and middle <= len(elements):
52.                 if elements[middle] == element:
53.                     prevMiddle = middle
54.                     middle = middle + direction
55.                 else:
56.                     same = False
57.             return prevMiddle
58.     return -1
59.
60.
61. def binarySearchClosest(elements,searchTerm):
62.     #search for the closet element in list that matchest the search term
63.     lower = 0
64.     upper = len(elements) - 1
65.     lastLower = lower
66.     lastUpper = upper
67.     found = False
68.     loc = 0
69.     while lower <= upper:
70.         #print(elements[lower:upper+1])
71.         middle = calculateMiddle(lower,upper)
72.         #print(lower,middle,upper,elements[middle])
73.         #if the middle element is higher than the search term then return the second half of the list else the first half
74.         if elements[middle] > searchTerm:
75.             lastUpper = upper
76.             upper = middle -1
77.             #print(elements[lower:upper+1])
78.         elif elements[middle] < searchTerm:
79.             lastLower = lower
80.             lower = middle + 1
81.             #print(elements[lower:upper+1])
82.         else:
83.             return (searchTerm,middle)
84.     #iterate through list between lastLower and lastUpper
85.     #this next line is only called if the search term is not found
86.     #the sublist is the list prior to the last list division
87.     return checkSublist(lastLower,lastUpper,elements,searchTerm)
88.
89. def checkSublist(lastLower,lastUpper,elements,searchTerm):
91.     #loop through all elements and find the item that is closest to the search term
92.     diff = -1
93.     closest = -1
94.     ndiff = 0
95.     loc = lastLower
96.     locClosest = 0
97.     #print(lastLower,lastUpper)
98.     for item in elements[lastLower:lastUpper+1]:
99.         ndiff = calculateDifference(searchTerm,item)
100.         #print(item,item,searchTerm,ndiff)
101.         if diff == -1 or ndiff < diff:
102.             diff = ndiff
103.             closest = item
104.             locClosest = loc
105.         loc += 1
106.     return closest, locClosest
107.
108. def calculateDifference(element,currentTerm):
109.     return abs(element - currentTerm)
110.
111. def calculateMiddle(lower,upper):
112.     #calculate the middle value between the upper and lower limits of the current sublist
113.     return int((upper + lower) / 2)
114.
115. def searchResult(element,closest, location):
116.     if closest  == '':
117.         if location == -1:
118.             print(str(element) + ' is not in the list')
119.         else:
120.             print(str(element) + ' was found as index ' + str(location))
121.     else:
122.         print('The closest element was {} and was found at index {}'.format(closest,location))
123.
124.
125.
126.
127.
128. elements = sorted((generateRandomList(25)))
129. print(elements)
130. searchTerm = float(getItem())
131.
132. print('-----')
133. print('Binary Search')
134. location = binarySearch(elements,searchTerm)
135. searchResult(searchTerm,'',location)
136.
137.
138. print('-----')
139. print('Binary Search Left')
140. #elements = [1, 2, 2, 2, 4, 4, 4, 4, 5, 6, 7, 8, 9]
141. #print(elements)
142. location = binarySearchSame(elements,searchTerm,-1)
143. searchResult(searchTerm,'',location)
144.
145. print('-----')
146. print('Binary Search Right')
147. location = binarySearchSame(elements,searchTerm,1)
148. searchResult(searchTerm,'',location)
149.
150.
151.
152. print('-----')
153. print('Binary Search Closest')
154. closest, location = binarySearchClosest(elements,searchTerm)
155. searchResult(searchTerm,closest, location)
156.
157.
158.