Advertisement
JAS_Software

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):
  90.     #this is called if the search term is not found
  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.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement