MOD 6 LAB - ORDERED LIST ADT

Can you please show me the code with an explanation on how to implement an O(logn) binary search with the code in the picture?

ode is intended for safe code brousing. Trust this window to enable all features. Manage Leam More sers > iamla > AppData > Local > Temp > Temp2_lab6_starter.zip > Z lab6.py > Qg OrderedList klass 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(1ist(items)) if items is not None else list() (2) 50 In 1, Col 1 Spaces: 4 UTF-8 sintended for safe code browsing. Trust this window to enable all features. Manage Leam More iamla > AppData > Local > Temp > Temp2_lab6_starter.zip > lab6.py > G OrderedList def _contains_(self, item): "." "returns true if there is an item of the list equal to item. "w" return self._bs(item, , 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 =1en(L)//2 \# base case - we found the item if item ==L[ median ]: return True iamla > AppData > Local > Temp > Temp2_lab6_starter.zip > Bab6.py > L G OrderedList * base case - we found the item if item == L [median]: return True * item is in smaller half elif item +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 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. Submission At a minimum. submit the following files