Implementation
Below is the full implementation of the program.
import pygame
import random
pygame.font.init()
# main window
width, height = 1001, 650
window = pygame.display.set_mode((width, height))
# window caption
pygame.display.set_caption("Ternary Search Visualizer")
# main array containing all the items
main_arr = [0]*101
# item which needs to be searched in the array
item_to_search = 0
# boolean to track if the item is found or not
item_found = False
# each item corresponds to the color of each bar
arr_color = [(41, 52, 98)]*101
arr_color_index = 0
color = [(41, 52, 98), (242, 76, 76), (236, 155, 59), (247, 215, 22)]
# Fonts
fnt = pygame.font.SysFont("comicsans", 60)
fnt1 = pygame.font.SysFont("comicssans", 30)
fnt2 = pygame.font.SysFont("comicssans", 40)
# generate new array with random values
def gen_random_arr():
for i in range(1, 101):
arr_color[i] = color[0] # To make all bars of same color
main_arr[i] = random.randrange(1, 100)
#sorting
main_arr.sort()
# function to draw array
def draw():
pygame.draw.line(window, (0, 0, 0), (0, 560), (1000, 560), 7)
text = fnt1.render("Press 'Enter' to Start", 1, (0, 0, 0))
window.blit(text, (10, 580))
text = fnt1.render("Press 'N' to Generate New Array", 1, (0, 0, 0))
window.blit(text, (10, 610))
text = fnt2.render("Enter the Number to Search: " + str(item_to_search), 1, (0, 0, 0))
window.blit(text, (400, 590))
# width of each bar
item_width = 9
# drawing array
for i in range(1, 101):
start_pos = (i*10 - 5, 550 - ((main_arr[i] * (550/100))))
end_pos = (i*10 - 5, 554)
pygame.draw.line(window, arr_color[i], start_pos, end_pos, item_width)
# if item found in array.. print this message
if item_found == 1:
text = fnt.render("Item Found.. Press `R` to Reset", 1, (0, 0, 0))
window.blit(text, (10, 50))
elif item_found == -1:
text = fnt.render("Item not found.. Press `R` to Reset", 1, (0, 0, 0))
window.blit(text, (10, 40))
# function to draw the updates on window
def refresh():
window.fill((214, 214, 194))
draw()
pygame.display.update();
pygame.time.delay(150)
# Ternary Search Implementation
def ternarySearch(array, key):
# finding leftmost and right most element in the array
l = 1
r = len(array)-1
# Loop till variable pointing to leftmost element
# becomes greater than or equal to the variable pointing to
# rightmost element
while l <= r:
pygame.event.pump()
# changing the color of left and right element in the array
arr_color[l] = color[1]
arr_color[r] = color[1]
# finding mid1 and mid2
mid1 = l+(r-l)//3
mid2 = r-(r-l)//3
# changing color of mid1 bar and mid2 bar
arr_color[mid1] = color[3]
arr_color[mid2] = color[3]
# drawing the updates on screen
refresh()
pygame.event.pump()
refresh()
refresh()
# again changing the color
arr_color[l] = color[0]
arr_color[r] = color[0]
arr_color[mid1] = color[0]
arr_color[mid2] = color[0]
# checking if the term we are searching for
# is present at any mid index
if key == array[mid1]:
arr_color[mid1] = color[2]
return 1
if key == array[mid2]:
arr_color[mid1] = color[2]
return 1
# if key is not present in the mid and is smaller than middle element
# then we update our right variable so that we can search in the left
# part of the array
if key < array[mid1]:
r = mid1-1
elif key > array[mid2]:
l = mid2+1
else:
l = mid1+1
r = mid2-1
refresh()
# return -1 if element not found in the array
return -1
# Generating random array when program loads up
gen_random_arr()
# main loop
quit = False
while not quit:
# background color
window.fill((214, 214, 194))
# track user events
for event in pygame.event.get():
if event.type == pygame.QUIT:
quit = True
# checks if user presses any key or not
if event.type == pygame.KEYDOWN:
# if the key pressed by user is 'r'
# then refresh our program
if event.key == pygame.K_r:
item_found = False
item_to_search = 0
gen_random_arr()
# if the key pressed is equal to n
# then generate new random array
if event.key == pygame.K_n:
gen_random_arr()
# if user presses Enter key and the item we want to search is
# not equal to zero then we initiate
# our ternarySearch algorithm
if event.key == pygame.K_RETURN and item_to_search != 0:
item_found = ternarySearch(main_arr, item_to_search)
# all the below events add the value corresponding to our
# key pressed into the search variable
if event.key == pygame.K_0:
item_to_search = item_to_search*10
if event.key == pygame.K_1:
item_to_search = item_to_search*10+1
if event.key == pygame.K_2:
item_to_search = item_to_search*10+2
if event.key == pygame.K_3:
item_to_search = item_to_search*10+3
if event.key == pygame.K_4:
item_to_search = item_to_search*10+4
if event.key == pygame.K_5:
item_to_search = item_to_search*10+5
if event.key == pygame.K_6:
item_to_search = item_to_search*10+6
if event.key == pygame.K_7:
item_to_search = item_to_search*10+7
if event.key == pygame.K_8:
item_to_search = item_to_search*10+8
if event.key == pygame.K_9:
item_to_search = item_to_search*10+9
draw()
pygame.display.update()
pygame.quit()
You can also try this code with Online Python Compiler
Output
Frequently Asked Questions
What is pygame used for?
The pygame library is a free, open-source Python module for creating games and other multimedia applications. Pygame is a cross-platform game engine built on top of the SDL (Simple DirectMedia Layer) development framework.
Is ternary search faster than binary?
We usually omit the constants when calculating the Time complexity of any algorithm. However, the constants in Ternary search are bigger than those in Binary search. As a result, the Ternary search takes more time to complete its execution.
How does ternary search differ from binary search?
We divide the sorted array into two halves (and decide which one has the key) until we find the element we're looking for in binary search, whereas we divide the array into three halves (and determine which one has the key) until we find the element we're looking for in ternary search.
Conclusion
In this article, we have extensively discussed What ternary search is, and how we can make a visualizer using pygame to visualize ternary search.
We hope that this blog has helped you enhance your knowledge about Ternary Search and Pygame and if you would like to learn more, check out our articles on our Website.
Check out our articles like PyGame Library in Python, Building Snake Game using PyGame: Part 1, and Building Snake Game using PyGame: Part 2 to enhance your knowledge regarding Pygame. Also, have a look at Python libraries and their features to learn more about Python.
Check out Interview Experiences and Interview Preparation Resources to crack the technical interviews at top Product-based companies like Amazon, Microsoft, Uber, etc. Visit Coding Ninjas Studio Guided Path to Upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and more.
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!
34+ registered 
