Table of contents
1.
Introduction
2.
Getting Started
3.
Implementation
4.
Frequently Asked Questions
4.1.
What is pygame used for?
4.2.
Is ternary search faster than binary?
4.3.
How does ternary search differ from binary search?
5.
Conclusion
Last Updated: Mar 27, 2024

Ternary Search Visualization using Pygame in Python

Author Harsh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Ternary Search is a searching algorithm, which is very similar to Binary Search. The difference is that in binary search we divide the array into 2 parts whereas in ternary search we divide the array into 3 parts.
In this blog, we’ll make a Ternary search visualizer which will help us to understand how ternary search works.

Getting Started

As we are developing the program using pygame, let's first import and initialize few things:

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)
You can also try this code with Online Python Compiler
Run Code

 

The above-written code will do some initial setup like defining the array, font and font size, caption of the window, setting window height and width, and a few more things.
After this, we need to define a few functions which will help us to complete the program. Let’s discuss each one of them one by one.

  1. gen_random_arr(): Generate Random Array, the functionality of the function is self-explanatory, it generates the random array of size 101 (we defined the size in the initial setup).
     
  2. draw(): As the name suggests, this function draws the array to the screen. It also draws some information that helps the user to interact with the program.
     
  3. refresh(): updates the window, by calling the draw function and setting the background color.
     
  4. ternarySearch(array, key): Now this is our main function, Ternary Search is implemented in the function and after every change, we update the arr_color array and then call the refresh() function to update the screen.
     

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
Run Code

 

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 PythonBuilding 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!

Live masterclass