Question
Starter Code: class OrderedList: def __init__(self, items=None): Initialize an ordered list. If `items` is specified, the OrderedList starts with the items in that collection self._L
Starter Code:
class OrderedList:
def __init__(self, items=None):
"""Initialize an ordered list. If `items` is specified, the OrderedList starts with the items in that collection"""
self._L = sorted(list(items)) if items is not None else list()
def add(self, item):
"""adds item to the list"""
self._L.append(item)
self._L.sort()
def remove(self, item):
"""removes the first occurrence of item from the list. Raise a RuntimeError if the item is not present."""
if not item in self: raise RuntimeError(f"{item} not in OrderedList")
self._L.remove(item) # O(n) to find, then O(n) to remove
def __getitem__(self, index):
"""returns the item with the given index in the sorted list. This is also known as selection."""
return self._L[index]
def __iter__(self):
"""returns an iterator over the ordered list that yields the items in sorted order. Required for `for` loops."""
return iter(self._L)
def __len__(self):
"""returns the length of the ordered list."""
return len(self._L)
def __contains__(self, item):
"""returns true if there is an item of the list equal to item."""
return self._bs(item, 0, len(self)) # You'll have to implement _bs() for this to work
# The lines below implement contains with different algs.
# Feel free to try them out, but they are both too slow
# to pass the tests in gradescope (O(n) instead of O(logn)).
# return self._contains_list(item) # uses python's default list-search
# return self._contains_bs_slow(item) # uses a slow version of binary-search (slicing)
def _contains_list(self, item):
"""returns True iff there is an item of the list equal to item."""
return item in self._L # Works, but slow (O(n))
def _contains_bs_slow(self, item):
return self.__contains_bs_slow(self._L[:], item)
def __contains_bs_slow(self, L, item):
"""searches L for item. This is slow since it slices L at every level of recursion"""
# base case - item not in list
if len(L) == 0: return False
median = len(L) // 2
# base case - we found the item
if item == L[median]: return True
# item is in smaller half
elif item
# item is in bigger half
else: return self.__contains_bs_slow(L[median + 1:], item)
# TODO: Implement O(logn) binary search
def _bs(self, ???):
"""searches for item using `left` and `right` indices instead of slicing"""
# base case - item not in list
# base case: found item
# item is in smaller half
# item is in bigger half
Mod 6 Lab - Ordered List AD'I The Ordered List ADT is similar to a list, but adds the requirement that items remain sorted: - add( item) - adds item to the list. - remove(item) - removes the first occurrence of item from the list. Raise a RuntimeError if the item is not present. - getitem(index) - returns the item with the given index in the sorted list. This is also known as selection. - contains(item) - returns True iff there is an item of the list equal to item. - iter - returns an iterator over the ordered list that yields the items in sorted order. - len - returns the length of the ordered list. We have provided a working Ordered List in lab6. py. The starter code includes 3 ways of implementing contains: -_bs(???) - up to you to implement. Should be O(logn). -_contains_list(item) - uses python's built-in list search. O(n). - contains_bs_slow(item) - uses a binary search built on slicing. O(n). def __contains__(self , item): return self._bs(item, 0, len(self)) \#Requires_bs() for this to work \# alternative search algorithms: \# return self._contains_list(item) \# uses python's default list-search \# return self._contains_bs_slow(item) \# uses a slow version of binary-search (slicing) Deliverable - _bs() Implement a O(logn) binary search. You'll need to pass left/right indices insted of list slices with each recursive call to do this. Note that TesetLab6.py, included with the starter code, tests the contains method. If you are struggling to debug with the tests provided, try writing your own
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started