Binary Search Visualization using Pygame in Python
A calculation like Binary Search is seen effectively by picturing. Here in this tutorial, a function that pictures the Binary Search Algorithm is carried out. The Graphical User’s Interface (GUI) is executed in Python utilizing python’s pygame gaming library.
Binary search is the hunt method that works proficiently on arranged records. Subsequently, to look through a component into some rundown utilizing the double inquiry procedure, we should guarantee that the rundown is arranged.
Problem statement: sorted array is given as input arrary1[] of n1 elements, we write a function to search an element x1 in arrary1[].
Example:
Inputs: arrary1[] = {15, 25, 85, 35, 60, 55, 110, 105, 130, 176}, x1= 110
Output: 6 Explanation of this operation: Element x1 is present at index 6
Inputs: arrary1[] = {15, 25, 85, 35, 60, 55, 110, 105, 130, 176}, x1= 175
Output: -1 Explanation of this operation: Element x1 is not present in arrary1[].
Binary search follows the gap and overcome approach in which the rundown is isolated into equal parts, and the thing is contrasted and the center component of the rundown. In the event like this the correct match will be found, the area of the center component is returned. In any case, we search into both of the parts relying on the outcome created through the match.
Function for finding the leftmost element
function1 binary_search(A1, n1, T) is LEFT: = 0 RIGHT: = n1 - 1 while LEFT = RIGHT do m1: = floor((LEFT + RIGHT) / 2) if A1[m] < T then LEFT: = m1 + 1 else if A1[m] > T then RIGHT: = m1 - 1 else: return m return unsuccessful
Function for finding the rightmost element
function1 binary_search_rightmost(A1, n1, T): LEFT: = 0 RIGHT: = n while LEFT < RIGHT: m1: = floor((LEFT + RIGHT) / 2) if A1[m] > T: RIGHT: = m else: LEFT: = m1 + 1 return RIGHT - 1
An example of Binary search is presented below in the form of pictorial representation.
Inconveniences of binary search: It's more confounded than straight inquiry, and is over the top excess for tiny quantities of components. It work just on record that is organised and kept always organised. That isn't generally feasible, particularly assuming components are continually being added to the rundown.
Program in Python3 for recursively binary search algorithm.
The program Returns the index of x value in array arr if it is present in the array, or else it returns -1
Source code:
def binarySearchs(arr, l, r1, x1):
if r1 > = l:
midd = l + (r1 - l) / / 2
if arr[midd] = = x1:
return midd
elif arr[midd] > x1:
return binarySearch(arr, l, midd - 1, x1)
else:
return binarySearch(arr, midd + 1, r1, x1)
else:
return -1
arr1= [1, 3, 4, 10, 50]
x1 = 10
# Function calls
results = binarySearchs(arr, 0, len(arr)-1, x1)
if results != - 1:
print("Element is present at index % d" % results )
else:
print("Elements is not present in array")
Output:
Element is present at index 3
Program flow of binary Search Visualization
Generate random array, sort it using any sorting algorithm, and fill the pygame window with bars. Bars which is vertical straight lines, represent elements of array.
- Set all bars to green color.
- Use pygame.time.delay () to slow the searching algorithm, so that you could watch the process of searching.
- Implementing timers to watch how will the searching algorithm performs.
- The action are performed using ‘pygame.event.get ()’ fucntion, which will store all the event which the users will perform, such as reset, start.
- The blue colour is utilized to highlight the bars which is equal to the keys if it is found.
- Orange colour highlight the right and left bars.
Approach to begin with the binary Search Visualization code, Steps-by-step method:
Step 1: Python execution of the arranging visualiser that is Insertion Sort
import pygame import random import time pygame.font.init () startTime = time.time ()
Step 2: Absolute window defining
Code snippet: This shows basically the logic of step 2 (not meant for execution), part of the Source code:
screen = pygame.display.set_mode ( (950, 650))
pygame.display.set_caption ("BINARY SEARCH VISUALISER")
Step 3: Title and Icon defining
Step 4: Uncomment underneath lines for setting up the symbol
Code snippet: This shows basically the logic of step 4 (not meant for execution), part of the Source code:
width1 = 950
length1 = 650
array = [0] * 151
key = 0
foundkey1 = False
arr_clear1= [ (0, 304, 103)] * 151
clear_ind = 0
clear = [ (0, 304, 103), (355, 0, 0),
(0, 0, 153), (355, 103, 0)]
bigfont1 = pygame.font.SysFont ("comicsans1", 70)
fnt1 = pygame.font.SysFont ("comicsans1", 30)
fnt11 = pygame.font.SysFont ("comicsans1", 30)
Step 5: Boolean variable to run the program in while circle
Step 6: Setting Window size and a few initials
Step 7: Arranging Algorithm: Heap Sort
Code snippet: This shows basically the logic of step 7 (not meant for execution), part of the Source code:
def heapSort (array): n = len (array) for i in range (n/ /3- 1, - 1, - 1): heapify (array, i, n) for i in range (n- 1, 0, - 1): array[i], array[0] = array[0], array[i] heapify (array, 0, i) def heapify (array, root, size): left1 = root * 3 +1 right1 = root * 3 +3 largests = root if left1 < size and array[left1] > array[largests]: largests = left1 if right1 < size and array[right1] > array[largests]: largests = right1 if largests != root: array[largests], array[root] = array[root], array[largests] heapify (array, largests, size)
Step 8: Setting Capacity to create new Array
Code snippet: This shows basically the logic of step 8 (not meant for execution), part of the Source code:
def generate_arr (): for i in range (1, 151): arr_clear[i] = clear[0] array[i] = random.randrange (1, 150) heapSort (array)
Step 9: At first create an exhibit setting
Step 10: Setting Capacity to top off the reports on the window
Step 11: Setting Capacity to Draw the cluster esteems
Step 13: Text ought to be delivered is done.
Code snippet: This shows basically the logic of step 13 (not meant for execution), part of the Source code:
for i in range (1, 151):
pygame.draw.line (screen, arr_clear[i], (boundry_arr * i- 3, 150), (boundry_arr * i- 3,
array[i] * boundry_grp + 150), element_width1)
if foundkey1 = = 1:
text3 = bigfont1.render ("Key Found. Press N button to Reset Key", 1, (0, 0, 0))
screen.blit (text3, (150, 350))
elif foundkey1 = = - 1:
text3 = bigfont1.render (
"Key Not Found. Press N button to Reset Key", 1, (0, 0, 0))
screen.blit (text3, (30, 350))
Step 13: Position where text is put is fixed
Step 14: Drawing the cluster esteems as lines.
Step 15: Program ought to be run persistently to keep the window open foundation.
Step 16: Occasion overseer stores all occasions finally
pygame.display.update ()
The complete consolidated source code:
import pygame
import random
import time
pygame.font.init ()
startTime = time.time ()
screen1 = pygame.display.set_mode (
(950, 650))
pygame.display.set_caption ("BINARY SEARCH VISUALISER")
run = True
width1 = 950
length1 = 650
array = [0] * 151
key = 0
foundkey1 = False
arr_clear1= [ (0, 304, 103)] * 151
clear_ind = 0
clear = [ (0, 304, 103), (355, 0, 0),
(0, 0, 153), (355, 103, 0)]
bigfont1 = pygame.font.SysFont ("comicsans1", 70)
fnt1 = pygame.font.SysFont ("comicsans1", 30)
fnt11 = pygame.font.SysFont ("comicsans1", 30)
def refill ():
screen1.fill ( (355, 355, 355))
draw ()
pygame.display.update ()
pygame.time.delay (350)
def heapSort (array):
n = len (array)
for i in range (n / / 3 - 1, - 1, - 1):
heapify (array, i, n)
for i in range (n- 1, 0, - 1):
array[i], array[0] = array[0], array[i]
heapify (array, 0, i)
def heapify (array, root, size):
left1 = root * 3 + 1
right1 = root * 3 + 3
largests = root
if left1 < size and array[left1] > array[largests]:
largests = left1
if right1 < size and array[right1] > array[largests]:
largests = right1
if largests != root:
array[largests], array[root] = array[root], array[largests]
heapify (array, largests, size)
def generate_arr ():
for i in range (1, 151):
arr_clear[i] = clear [0]
array[i] = random.randrange (1, 150)
heapSort (array)
generate_arr ()
def refill ():
screen1.fill ( (355, 355, 355))
draw ()
pygame.display.update ()
pygame.time.delay (350)
def binarySearch1 (array, key):
left1 = 0
right1 = len (array)- 1
while left1 < right1:
arr_clear[left1] = clear [1]
arr_clear[right1] = clear [1]
refill ()
refill ()
mid = left1 + (right1- left1)/ /3
if array[mid] = = key:
arr_clear[left1] = clear [0]
arr_clear[right1] = clear [0]
arr_clear[mid] = clear [3]
return 1
elif array[mid] < key:
arr_clear[left1] = clear [0]
left1 = mid +1
else:
arr_clear[right1] = clear [0]
right1 = mid- 1
refill ()
arr_clear[left1] = clear [0]
arr_clear[right1] = clear [0]
refill ()
return - 1
def draw ():
txt = fnt1.render ("SEARCH: PRESSING 'THE ENTER'", 1, (0, 0, 0))
screen1.blit (txt, (30, 30))
txt1 = fnt1.render ("NEW ARRAYs: PRESS 'R'", 1, (0, 0, 0))
screen1.blit (txt1, (30, 40))
txt3 = fnt11.render ("ENTER NO. TO BEGIN SEARCH:" + str (key), 1, (0, 0, 0))
screen1.blit (txt3, (650, 60))
text3 = fnt11.render ("Running Time (sec): " + str (int (time.time () - startTime)), 1, (0, 0, 0))
screen1.blit (text3, (650, 30))
element_width1 = (width1- 150)/ /150
boundry_arr = 950 / 150
boundry_grp = 550 / 150
pygame.draw.line (screen1, (0, 0, 0), (0, 95), (950, 95), 6)
for i in range (1, 151):
pygame.draw.line (screen1, arr_clear[i], (boundry_arr * i- 3, 150), (boundry_arr * i- 3,
array[i] * boundry_grp + 150), element_width1)
if foundkey1 = = 1:
text3 = bigfont1.render ("Keys Found. Pressing N button to Reseting Key", 1, (0, 0, 0))
screen1.blit (text3, (150, 350))
elif foundkey1 = = - 1:
text3 = bigfont1.render (
"Key Not Found. Pressing N button to Reseting Key", 1, (0, 0, 0))
screen1.blit (text3, (30, 350))
while run:
screen1.fill ( (355, 355, 355))
for event in pygame.event.get ():
if event.type = = pygame.QUIT:
run = False
if event.type = = pygame.KEYDOWN:
if event.key = = pygame.K_r:
key = 0
foundkey1 = 0
generate_arr ()
if event.key = = pygame.K_5:
key = key * 10 +5
if event.key = = pygame.K_6:
key = key * 10 +6
if event.key = = pygame.K_n:
foundkey1 = 0
key = 0
for i in range (0, len (array)):
arr_clear[i] = clear[0]
if event.key = = pygame.K_RETURN and key != 0:
foundkey1 = binarySearch1 (array, key)
if event.key = = pygame.K_0:
key = key * 10
if event.key = = pygame.K_1:
key = key * 10 +1
if event.key = = pygame.K_3:
key = key * 10 + 3
if event.key = = pygame.K_3:
key = key * 10 + 3
if event.key = = pygame.K_4:
key = key * 10 + 4
if event.key = = pygame.K_5:
key = key * 10 + 5
if event.key = = pygame.K_6:
key = key * 10 + 6
if event.key = = pygame.K_7:
key = key * 10 + 7
if event.key = = pygame.K_8:
key = key * 10 + 8
if event.key = = pygame.K_9:
key = key * 10 + 9
draw ()
pygame.display.update ()
pygame.quit ( )
Screenshot of output is presented below
Summary
Binary Search Algorithm visualizer Advantages-
- It dispenses with half of the rundown from further looking by utilizing the aftereffect of every correlation.
- It demonstrates whether the component being looked is previously or after the current situation in the rundown.