CSE 30 Fall 2021 – Homework 3Python二分查找作业与答案



CSE 30 Fall 2021 – Homework 3


Please disregard the YOUR NAME and COLLABORATORS above. They are put there atomatically by the grading tool. You can find instructions on how to work on a homework on Canvas. Here is a short summary:

Submitting your work To submit your work:

First, click on “Runtime > Restart and run all”, and check that you get no errors. This enables you to catch any error you might have introduced, and not noticed, due to your running cells out of order.

Second, download the notebook in .ipynb format (File > Download .ipynb) and upload the

.ipynb file to this form.

You can submit multiple times; the last submission before the deadline is the one that counts.

Homework format

For each question in this notebook, there is:

A text description of the problem.

One or more places where you have to insert your solution. You need to complete every place marked:

# YOUR CODE HERE 在下面填写你的代码


and you should not modify any other place.


One or more test cells. Each cell is worth some number of points, marked at the top. You should not modify these tests cells. The tests pass if no error is printed out: when there is a statement that says, for instance:

assert x == 2


then the test passes if x has value 2, and fails otherwise. You can insert a print(x) (for this case!) somewhere if you want to debug your work; it is up to you.



Your code will be tested both according to the tests you can see (the assert statements you can see), and additional tests. This prevents you from hard-coding the answer to the particular questions posed. Your code should solve the general intended case, not hard-code the particular answer for the values used in the tests.

Please do not delete or add cells! The test is autograded, and if you modify the test by adding or deleting cells, even if you re-add cells you delete, you may not receive credit.

Please do not import modules that are not part of the standard library. You do not need any, and they will likely not available in the grading environment, leading your code to fail.

If you are inactive too long, your notebook might get disconnected from the back-end. Your work is never lost, but you have to re-run all the cells before you continue.

You can write out print statements in your code, to help you test/debug it. But remember: the code is graded on the basis of what it outputs or returns, not on the basis of what it prints.

TAs and tutors have access to this notebook, so if you let them know you need their help, they can look at your work and give you advice.


Each cell where there are tests is worth a certain number of points. You get the points allocated to a cell only if you pass all the tests in the cell.

The tests in a cell include both the tests you can see, and other, similar, tests that are used for grading only. Therefore, you cannot hard-code the solutions: you really have to solve the essence of the problem, to receive the points in a cell.

Code of Conduct


Work on the test yourself, alone.

You can search documentation on the web, on sites such as the Python documentation sites, Stackoverflow, and similar, and you can use the results.

You cannot share your work with others or solicit their help.



Problem: Dicothomic Search



You are given a sorted list l , 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:


for el in l:

if el == x:



or you can do the same with l.index(x) , but these approaches do not take advantage of the fact that l is sorted, and take an amount of time that is proportional to the length of the list l : 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(l, x, i, k) which searches for the earliest occurrence of  x in the list  l 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(l, x, 0, len(l)) . The function  search should work as follows:

If k <= i , there is nowhere you can search, and you return None . If k = i + 1 , then you know what to check!

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 l[j] . Based on that, you decide whether to search (calling search recursively) from i to j , or from j 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 l[k] < …


then that code would be accessing l[k] twice. You may want to cache the value of l[k] in an intermediate place to avoid such accesses:


lk = l[k]

if lk == …

if lk < …



matters: do not access twice in a row the same list element; rather, cache its value.

This is only an example; the actual piece of code is not like the one above, but the idea is what



def binary_search(l, x): “””Helper function.”””

return search(l, x, 0, len(l))



## Here is a place for you to play with your code.





First, let’s do a small sanity check, checking that at least you find the correct element.



# 5 points.


assert binary_search([1, 2, 3, 4, 5, 6], 2) == 1

assert binary_search([1, 2, 3, 5, 6, 7], 4) is None


# We did say, the earliest occurrence.

assert binary_search([1, 2, 3, 3, 3, 4, 5], 3) == 2

assert binary_search([1, 2, 2, 2, 2, 3, 4, 5], 2) == 1

assert binary_search([1, 1, 1, 1, 1, 2, 3], 1) == 0



To keep you honest, we implement two tricks. First, we will not let you work on a list, but rather, on a WeakList, which counts how many times it has been accessed, and if you access it too many times, it raises an exception. This will force you to implement dicothomic search rather than just scanning the list.

To help in debugging, we make a WeakList also print out where it is accessed.



import math



class TooManyAccesses(Exception): pass


class WeakList(object):


def   init  (self, *args, verbose=True):

“””You create a tired list passing it the elements as arguments.”””

self.l = list(args) # Do not rely on this being called l… it will be renamed in gra self.num_accesses = 0

self.max_accesses = int(math.log2(len(self.l))) + 2 self.verbose = verbose


def   len (self):

“””This implements the len() method.””” return len(self.l)


def   getitem  (self, i):

“””This implements the lookup via [i] syntax.””” if self.verbose:

print(“Accessed position”, i) self.num_accesses += 1

if self.num_accesses > self.max_accesses:

raise TooManyAccesses(“You have exceeded the maximum of {} accesses”.format(self. return self.l[i]



## Here is a place for you to play with your code.





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. l = WeakList(3, 4, 5, 6, 7, 8)

assert binary_search(l, 8) == 5


l = WeakList(3, 4, 4, 5, 7, 8)

assert binary_search(l, 4) == 1

l = WeakList(3, 4, 4, 5, 7, 8)

assert binary_search(l, 5) == 3

l = WeakList(3, 5, 6, 7)

assert binary_search(l, 8) is None



# 15 points. Now, some randomized tests. import random



for _ in range(1000):

n = random.randint(10, 100)

l = list(random.choices(list(range(100)), k=n)) l.sort()

k = random.randint(0, 99)

wl = WeakList(*l, verbose=False)

# print(“Searching”, l, “for”, k) if k in l:

# print(“It should be there.”) bs = binary_search(wl, k)

ix = l.index(k)

assert bs == ix, “Error: l: {}, k: {}, index: {}, binary: {}”.format(l, k, ix, bs) else:

# print(“It should not be there.”)

assert binary_search(wl, k) is None, “Error: {} found in {}”.format(k, l)




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.


from bdb import Bdb import sys

import traceback


class NonRecursive(Exception): pass

class RecursionDetector(Bdb): def do_clear(self, arg):



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





def test_recursion(func, depth=1):

detector = RecursionDetector(depth=depth) detector.set_trace()


r = func() except:

traceback.print_exc() r = None


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


# 15 points: Let’s check that you solved the problem through recursion. for _ in range(1000):

n = random.randint(10, 100)

l = list(random.choices(list(range(100)), k=n)) l.sort()

k = random.randint(0, 99)

wl = WeakList(*l, verbose=False) idx = test_enough_recursion(wl, k) if k in l:

assert l.index(k) == idx else:

assert idx is None

本站所有作品,教程等皆为原创,版权所有。只供个人及单位内部研究使用,对外展示或传播必需经本站同意,且注明来自本站。培训机构等用本站资源培训学生,需经本站授权。一旦付款,表示同意本站知识付费原则:数字商品,不支持退款。亦可直接向微信号scratch8付款购买。入住QQ群:225792826 和爱好者共同交流,并且能下载免费提供的Python资源(需提供真实姓名才可入群)
李兴球的博客_Python创意编程技术前沿_pygame » CSE 30 Fall 2021 – Homework 3Python二分查找作业与答案














Python名堂多,趣味到处有,劈开机械手,帧帧是图片。速算达人之猫狮大战正在进行。 逐字动画不独享,自动生成皆有它。2行代码自动生成字幕gif动画。 Python之潮来临,我在安源区教师科技创新能力的Python讲座






喜爱春天的人儿啊 心地纯洁的人_Python逐行像素显示














虫子满屏爬_三bug多线程示例程序浅析 少儿Python视频课程A级简介




sb3转exe,sb3素材提取器,编程小子apk, 未公开的pygame游戏集/scratch/python少儿编程免费下载集合



李兴球博客 风火轮编程主页