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)
# 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()