please use python and # to explain what you are doing. please be aware there are hidden test

these pictures are all a part of one question.

you have to write code that runs the test AND hidden test perfectly. the code needed is for the test at the end that are labeled un green (ex. 5pts, 10pts) . the code should run the hidden test. I have reuploaded the photos.

Problem: Dicothomic Search Q You are given a sorted list 1, and you need to look into it for an element x. Of course, you could start looking at the beginning for x, and continue until you are done: Ex} for el in 1: if el == x: X or you can do the same with 1.index(x), but these approaches do not take advantage of the fact that 1 is sorted, and take an amount of time that is proportional to the length of the list 1: on average, you will find x about halfway through. When you search in a dictionary, you don't take this approach. If you look for "hedgehog", you open the dictionary in the middle, and based on that you decide whether to search in the first half or the second half. This continues until you narrow the range of search to a single page. We want to follow the same idea to search in our list. We ask you to write a recursive function search(1, x, i, k) which searches for the earliest occurrence of x in the list 1 from position i to position k - 1, inclusive, and returns the smallest index at which x has been found, or None if it has not been found. To find if x is in the list, you would call search(1, x, 0, len(1)). The function search should work as follows: If k i + 1, then there is more than one position to consider. You split the range you have to search in the middle, say, at j = i + (k - i) // 2, and then look at 1[j]. Based on that, you decide whether to search (calling search recursively) from i to j, or from ; to . . = k. Note: in this exercise, the whole point is to use recursion, and to avoid accessing the list too many times. If you have code that reads (for example): if l[k] == if 1[k] <...>- then that code would be accessing 1[k] twice. You may want to cache the value of 1[k] in an intermediate place to avoid such accesses: then that code would be accessing 1[k] twice. You may want to cache the value of 1[k] in an intermediate place to avoid such accesses: Q ik = 1[k] if lk == {x} if lk <... this is only an example the actual piece of code not like one above but idea what matters: do access twice in a row same list element rather cache its value. def search x i k for occurrence from position to inclusive using recursion. your here binary_search function. return len place you play with code. first let small sanity check checking that at least find correct element. o points. assert none="=" we did say earliest occurrence. keep honest implement two tricks. will work on weaklist which counts how many times it has been accessed and if too raises exception. force dicothomic than just scanning list. help debugging make also print out where accessed. import math class toomanyaccesses pass iii _init__ verb e="True):" create tired passing elements as arguments. self.q="list(args)" rely being called be renamed grading. self.num_accesses="0" self.max_accesses="int(math.log2" self.verbose="verbose" len_ implements method. ii _getitem_ lookup via syntax. self.verbose:> self.max_accesses: raise TooManyAccesses ("You have exceeded the maximum of {} accesses" .format(self.num_accesses)) return self.q[i] [] ## Here is a place for you to play with your code. # YOUR CODE HERE We can now test that you can find the earliest occurrence of an element in a list without accessing too many elements. [ ] # 5 points. Some simple tests. Q We can now test that you can find the earliest occurrence of an element in a list without accessing too many elements. [] # 5 points. Some simple tests. {x} 1 = WeakList(3, 4, 5, 6, 7, 8) assert binary_search(1, 8) == 5 1 = WeakList(3, 4, 4, 5, 7, 8) assert binary_search(1, 4) 1 1 = WeakList(3, 4, 4, 5, 7, 8) assert binary_search(1, 5) == 3 1 = WeakList(3, 5, 6, 7) assert binary_search(1, 8) is None # 15 points. Now, some randomized tests. import random for n in range (1000): = random.randint(10, 100) 1 = list(random.choices(list (range (100)), k=n)) 1. sort() k = random.randint(0, 99) wl = WeakList(*l, verbose=False) # print("Searching", i, "for", k) if k in 1: # print("It should be there.") bs = binary_search(wl, k) ix = 1.index(k) assert bs == ix, "Error: 1: {}, k: {}, index: {}, binary: {}".format(1, k, ix, bs) else: # print("It should not be there.") assert binary_search(wl, k) is None, "Error: {} found in {}".format(k, 1) Next, we know that students typically loathe recursion, and would rather write unfathomable goops of code rather than use a simple recursive solution. We are not talking about you obviously. But just to keep the other students honest, we define here a decorator that checks that the function is indeed called recursively. E: [] from bdb import Bdb Q Next, we know that students typically loathe recursion, and would rather write unfathomable goops of code rather than use a simple recursive solution. We are not talking about you obviously. But just to keep the other students honest, we define here a decorator that checks that the function is indeed called recursively. {x} from bdb import Bdb import sys import traceback class NonRecursive (Exception): pass class RecursionDetector (Bdb): def do_clear(self, arg): pass def _init__(self, depth=1): Bdb. _init__(self) self.depth = depth self.stack = [] self.passed = False def user_call(self, frame, argument_list): code = frame.f_code depth = sum( [code == c for c in self.stack]) if depth >= self.depth: self.passed = True self.stack.append(code) def user_return(self, frame, return_value): assert self.stack(-1] == frame.f_code self.stack.pop() def test_recursion(func, depth=1): detector = RecursionDetector (depth=depth) detector.set_trace() try: r = func() except: traceback.print_exc() r = None finally: sys.settrace (None) return r def test_enough_recursion(wl, el): "" "Tests that you do enough recursion when calling binary_search(wl, el)""" n = int(math.log2 (len(wl))) - 1 return test_recursion(lambda: binary_search(wl, el), depth=n) [] assert test_recursion(lambda: binary_search([2, 3, 4, 5, 5, 6, 7, 8, 10, 11, 12], 5)) == 3 II III [] def test_enough_recursion(wl, el): "" "Tests that you do enough recursion when calling binary_search(wl, el)" n = int(math.log2 (len(wl))) - 1 return test_recursion(lambda: binary_search(wl, el), depth=n) [] assert test_recursion(lambda: binary_search([2, 3, 4, 5, 5, 6, 7, 8, 10, 11, 12], 5)) == 3 ( # 15 points: Let's check that you solved the problem through recursion. for in range (1000): n = random.randint(10, 100) 1 = list(random.choices(list(range (100)), k=n)) 1. sort() k = random.randint(0, 99) wl = Weaklist(*l, verbose=False) idx = test_enough_recursion(wl, k) if k in 1: assert 1.index(k) == idx else: assert idx is None