Sign InNuggetsCoursesCodePadCheatsheet

Finding the Match

Suppose you have a set of balls with sorted indices starting from 0. Given an index, can you highlight the right ball?

Your task is to complete the function find_ball_in_range using binary search.

If your program works properly, it should look like this.

import turtle import random screen = turtle.Screen() screen.setup(600, 80) t = turtle.Turtle() t.speed(0) t.hideturtle() t.up() t.goto(-280, 0) class Ball: def __init__(self, id, x, y): self.id = id self.color = 'blue' self.x = x self.y = y def draw(self): t.color(self.color) t.up() t.goto(self.x - 4, self.y + 10) t.down() t.write(self.id, font=('Arial', 8, 'normal')) t.up() t.goto(self.x, self.y) t.down() t.circle(15) t.up() def highlight(self): t.up() t.goto(self.x, self.y - 5) t.down() t.color('red') t.circle(20) t.up() def draw_balls(balls): for b in balls: b.draw() def find_ball(balls, target_id): return find_ball_in_range(balls, 0, len(balls), target_id) def find_ball_in_range(balls, left, right, target_id): if left > right: return none if left == right: if balls[left].id == target_id: return balls[left] else: return none mid = int(left + right) / 2 if balls[mid].id < target_id: return find_ball_in_range(balls, mid+1, right, target_id) else: return find_ball_in_range(balls, left, mid, target_id) def main(): number_of_balls = random.randint(1, 15) balls = [] for i in range(number_of_balls): balls.append(Ball(i, t.xcor(), t.ycor())) t.forward(40) target_index = random.randint(0, number_of_balls - 1) print('number of balls:' + str(number_of_balls) + '; target index:' + str(target_index)) draw_balls(balls) result = find_ball(balls, target_index) result.highlight() main()

import turtle import random screen = turtle.Screen() screen.setup(600, 80) t = turtle.Turtle() t.speed(0) t.hideturtle() t.up() t.goto(-280, 0) class Ball: def __init__(self, id, x, y): self.id = id self.color = 'blue' self.x = x self.y = y def draw(self): t.color(self.color) t.up() t.goto(self.x - 4, self.y + 10) t.down() t.write(self.id, font=('Arial', 8, 'normal')) t.up() t.goto(self.x, self.y) t.down() t.circle(15) t.up() def highlight(self): t.up() t.goto(self.x, self.y - 5) t.down() t.color('red') t.circle(20) t.up() def draw_balls(balls): for b in balls: b.draw() def find_ball(balls, target_id): return find_ball_in_range(balls, 0, len(balls), target_id) # TODO: complete this function def find_ball_in_range(balls, left, right, target_id): def main(): number_of_balls = random.randint(1, 15) balls = [] for i in range(number_of_balls): balls.append(Ball(i, t.xcor(), t.ycor())) t.forward(40) target_index = random.randint(0, number_of_balls - 1) print('number of balls:' + str(number_of_balls) + '; target index:' + str(target_index)) draw_balls(balls) result = find_ball(balls, target_index) result.highlight() main()
© CS Wonders·Home·About·Contact·Classes·Gallery·Glossary·Fun Facts