import random random.seed = 1 class array: def __init__(self, valuelist): self.atos = valuelist.copy() # this variable is the array that holds the data def additem(self, value): # adds a item to the array self.atos.append(value) def printarray(self): # prints the self.atos print(self.atos) def __contains__(self, key): # To test the binary search change the "__linearsearch" to "__binsearch" return self.__binsearch(key) def __linearsearch(self, key): # Implements the linear search to find an item in the array for item in self.atos: if item == key: return True return False def __binsearch(self, key): temp = sorted(self.atos) # Implements the binary search to find an item in the array temp. This implements an iterative bin search algorithm. low = 0 high = len(temp) - 1 while low <= high: mid = (low + high) // 2 if temp[mid] == key: return True elif temp[mid] > key: high = mid - 1 else: low = mid + 1 return False def maximum(self): return self.__findksmallest(len(self.atos)) def minimum(self): return self.__findksmallest(1) def __findksmallest(self, k): # Implements the selection algorithm temp = self.atos[:] return self.__select(temp, 0, len(temp) - 1, k - 1) def __select(self, arr, l, r, k): if l == r: return arr[l] pivot = self.__partition(arr, l, r) if k == pivot: return arr[pivot] elif k < pivot: return self.__select(arr, l, pivot - 1, k) else: return self.__select(arr, pivot + 1, r, k) def __partition(self, arr, l, r): x = arr[r] i = l for j in range(l, r): if arr[j] <= x: arr[j], arr[i] = arr[i], arr[j] i += 1 arr[i], arr[r] = arr[r], arr[i]
can you explain the code with comments
import random
random.seed = 1
class array:
def __init__(self, valuelist):
self.atos = valuelist.copy() # this variable is the array that holds the data
def additem(self, value):
# adds a item to the array
self.atos.append(value)
def printarray(self):
# prints the self.atos
print(self.atos)
def __contains__(self, key):
# To test the binary search change the "__linearsearch" to "__binsearch"
return self.__binsearch(key)
def __linearsearch(self, key):
# Implements the linear search to find an item in the array
for item in self.atos:
if item == key:
return True
return False
def __binsearch(self, key):
temp = sorted(self.atos)
# Implements the binary search to find an item in the array temp. This implements an iterative bin search
low = 0
high = len(temp) - 1
while low <= high:
mid = (low + high) // 2
if temp[mid] == key:
return True
elif temp[mid] > key:
high = mid - 1
else:
low = mid + 1
return False
def maximum(self):
return self.__findksmallest(len(self.atos))
def minimum(self):
return self.__findksmallest(1)
def __findksmallest(self, k):
# Implements the selection algorithm
temp = self.atos[:]
return self.__select(temp, 0, len(temp) - 1, k - 1)
def __select(self, arr, l, r, k):
if l == r:
return arr[l]
pivot = self.__partition(arr, l, r)
if k == pivot:
return arr[pivot]
elif k < pivot:
return self.__select(arr, l, pivot - 1, k)
else:
return self.__select(arr, pivot + 1, r, k)
def __partition(self, arr, l, r):
x = arr[r]
i = l
for j in range(l, r):
if arr[j] <= x:
arr[j], arr[i] = arr[i], arr[j]
i += 1
arr[i], arr[r] = arr[r], arr[i]
return i
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
