Exponential Search Visualizer using PyQt5
In this article we will see how we can make a PyQt5 application which will visualize the Exponential search algorithm. Exponential search can also be used to search in bounded lists. Exponential search can even out-perform more traditional searches for bounded lists, such as binary search, when the element being searched for is near the beginning of the array. This is because exponential search will run in O(log i) time, where i is the index of the element being searched for in the list, whereas binary search would run in O(log n) time, where n is the number of elements in the list. 
GUI implementation steps : 1. Create a list of label according to the given list of numbers 2. Set their text, border, color and geometry with the respective gap from each other 3. Each label height should be proportional to the value of each number 4. Create a start and pause push button to start the searching and pause the searching 5. Create a result label to show the searching status Back end implementation steps : 1. Create label list corresponding to the given numbers 2. Create variable for the index used by exponential search and other variable used by binary search index and flag for searching and flag for binary and exponential search. 3. Add action to the push button their action should change the flag status i.e start action should make flag true and pause action should make flag false. 4. Create timer object which calls a method after every specific time 5. Inside the timer method check for the flag is flag is true begin the exponential search algorithm 6. Check if value lies within the range if not show output as not found else continue 7. Start finding value at index if found stop the search and show result else double the index value 8. Find the range in which value would be and start binary search and set the lower and upper value of binary search 9. Show result with the help of binary search
Below is the implementation
Python3
# importing librariesfrom PyQt5.QtWidgets import *from PyQt5 import QtCore, QtGuifrom PyQt5.QtGui import *from PyQt5.QtCore import *import sysclass Window(QMainWindow): # list of numbers number = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] def __init__(self): super().__init__() # setting title self.setWindowTitle("Exponential Search") # setting geometry self.setGeometry(100, 100, 600, 400) # calling method self.UiComponents() # showing all the widgets self.show() # method for widgets def UiComponents(self): # start flag self.start = False self.binary = False self.expo = True # list to hold labels self.label_list = [] # desired value self.desired = 8 # Exponential Search variable self.index = 1 # binary search variable self.first = 0 self.last = len(self.number) - 1 self.mid = 0 # local counter c = 0 # iterating list of numbers for i in self.number: # creating label for each number label = QLabel(str(i), self) # adding background color and border label.setStyleSheet("border : 1px solid black; background : white;") # aligning the text label.setAlignment(Qt.AlignTop) # setting geometry using local counter # first parameter is distance from left # and second is distance from top # third is width and fourth is height label.setGeometry(50 + c * 30, 50, 20, i * 10 + 10) # adding label to the label list self.label_list.append(label) # incrementing local counter c = c + 1 # creating push button to start the search self.search_button = QPushButton("Start Search", self) # setting geometry of the button self.search_button.setGeometry(100, 270, 100, 30) # adding action to the search button self.search_button.clicked.connect(self.search_action) # creating push button to pause the search pause_button = QPushButton("Pause", self) # setting geometry of the button pause_button.setGeometry(100, 320, 100, 30) # adding action to the search button pause_button.clicked.connect(self.pause_action) # creating label to show the result self.result = QLabel("To search : " + str(self.desired), self) # setting geometry self.result.setGeometry(350, 280, 200, 40) # setting style sheet self.result.setStyleSheet("border : 3px solid black;") # adding font self.result.setFont(QFont('Times', 10)) # setting alignment self.result.setAlignment(Qt.AlignCenter) # creating a timer object timer = QTimer(self) # adding action to timer timer.timeout.connect(self.showTime) # update the timer every 300 millisecond timer.start(300) # method called by timer def showTime(self): # checking if flag is true if self.start: # Exponential Search if self.expo: # if equal for index value 0 if self.number[0] == self.desired: # stop the searching self.start = False # show the result and make the label green self.result.setText("Found at index : 0" ) self.label_list[self.index].setStyleSheet( "border : 2px solid green;" "background-color : lightgreen") # if not equal else: # make the label grey self.label_list[0].setStyleSheet( "border : 1px solid black;" "background-color : grey") # double the value of index self.index = self.index * 2 # temporary stores index temp = self.index # checking if index is greater then the len of list if self.index >= len(self.number): # update the index self.index = len(self.number) - 1 # start binary search self.expo = False self.binary = True # set variable of binary search self.first = temp//2 self.last = self.index # if desired value is smaller if self.desired < self.number[self.index]: # start binary search self.expo = False self.binary = True # set binary search variables self.first = temp//2 self.last = self.index # if number is equal to the index value if self.number[self.index] == self.desired: # stop the search self.start = False # show result and make label color green self.result.setText("Found at index : " + str(self.index)) self.label_list[self.index].setStyleSheet( "border : 2px solid green;" "background-color : lightgreen") # if not equal else: # make label color grey self.label_list[self.index].setStyleSheet( "border : 1px solid black;" "background-color : grey") # binary search if self.binary: # implementing binary search # finding mid index self.mid = (self.first + self.last) // 2 # if first index become greater than last index if self.first > self.last: # make start flag false self.start = False # show output as not found self.result.setText("Not Found") # if mid value is equal to the desired value if self.number[self.mid] == self.desired: # make flag false self.start = False # show output in result label self.result.setText("Found at index : " + str(self.mid)) # set color of label to green self.label_list[self.mid].setStyleSheet( "border : 2px solid green; " "background-color : lightgreen") # if not equal to mid value else: # make color grey self.label_list[self.mid].setStyleSheet( "border : 1px solid black; " "background-color : grey") # mid value is higher if self.number[self.mid] > self.desired: # change last index self.last = self.mid - 1 # if mid value is smaller if self.number[self.mid] < self.desired: # change first index self.first = self.mid + 1 # method called by search button def search_action(self): # making flag true self.start = True # showing text in result label self.result.setText("Started searching...") # method called by pause button def pause_action(self): # making flag false self.start = False # showing text in result label self.result.setText("Paused")# create pyqt5 appApp = QApplication(sys.argv)# create the instance of our Windowwindow = Window()# start the appsys.exit(App.exec()) |
Output :
