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