Binary Search in Python (Recursive and Iterative)

There are different types of searches in data structures. Today we are going to learn about the Binary Search Algorithm, it’s working, and will create a Project for binary search algorithm using Python and its modules.

What is Binary Search Algorithm?

Binary Search Algorithm is a type of algorithm that works on the divide and conquer policy. The list data in this type is sorted in ascending order.

In the binary search algorithm, there is a data list(say l) and a number(say n) that is to be found. We keep on dividing the list into halves until we find the number. Let us look at an example-

Let us say we have a list l = [1,2,3,4,5,6,7,8,9,10] and we have to find the n=0

Now first we check the mid item. Use formula mid= item at (length of l/2). Here mid=5

Now it is visible that n is less than 5 so the l is now divided upto mid.

Our new list is as given below.

Again we check for mid. mid=3

It is visible that n is less than 3 so the l is now divided upto mid.

Our new list is as given below.

Our number is still not found so let us repeat the steps again.

Again.

Now we see that we are only left with a single number that is 1. Our n is not equal to 1 so here we will conclude that the number we were trying to find is not in the list.

There are two ways to implement Binary Search are-

1. Iterative Approach – In iterative approach the track record of the list is kept manually. This search completes when the search number is found or the two pointers (first and last) are met.

The algorithm for Iterative Approach is –

def binary_search(n, item):
    left, right= 0, len(n)
    while right > left:
        middle = (left + right) // 2
        if nums[middle] > item:
            right = middle
        elif nums[middle] < item :
            left = middle + 1
        else:
            return middle
    return None

2. Recursive Approach – In the recursive approach the function calls itself inside its body. The algorithm for Recursive Approach is –

def binary_search(n, item, start, end):
    middle = (start + end) // 2
    if start == end:
        return None
    if n[middle] > item:
        return binary_search(n, item, start, middle)
    elif nums[middle] < item:
        return binary_search(n, item, middle + 1, end)
    else:
        return middle

Binary Search Algorithm Project Details

We are going to create a project and test it using the same entries in the example. In this project we will just be making use of Tkinter Module to create a GUI using python. We will take the input of the number from the user.

In the project, we are going to use the iterative approach.

Project Prerequisites

To build this project we need to build a basic understanding of python concepts like loops. To create the GUI we need to install the Tkinter Module. Following is the command to install the Tkinter Module-

Pip install tk

Download the Source Code

Before proceeding ahead, download the source code for python binary search project from the following link: Python Binary Search Code

Steps To Create the Binary Search Algorithm Project in Python

Following are steps to create a Binary Search Algorithm Project.

1. Import the Required Modules

2. Creating the Binary Search Algorithm

3. Creating the GUI

1. Import the Required Modules:

from tkinter import *
import tkinter as tk

• Tkinter Module – To create a GUI in Python. Here we are using alias tk so that referring to the module is easier during the execution of the project.

2. Creating the Binary Search Algorithm:

• To implement the binary search algorithm, we have created a function named binary_search()

def binary_search():

def binary_search():
    l=e.get().split(" ")
    for i in range(0, len(l)):
        l[i] = int(l[i])
   
    num=(n.get())
    first = 0
    last = len(l)-1
    found = False
    while( first<=last and not found):
        mid = (first + last)//2
        if (l[mid] == num) :
                found = True
        else:
            if num < l[mid]:
                last = mid - 1
            else:
                first = mid + 1
    if found == True:
        Label(window, text="Number found in the list", font=('Calibri')).place(x=280,y=180)
    else:
        Label(window, text="Number NOT found in the list", font=('Calibri')).place(x=240,y=210)

• First using the get() method we get the value entered in the list. Note that this value is a single string right now. To convert it into elements and store it in a list we use the split(“ “) function. split(“ ”) function is used to split a string using a delimiter. Here our delimiter is space.
• Further in the project, we will compare a number with the element of the string so we need to convert the elements into Integer type. For this we take a loop and convert each element to int and save it in the list again. Conversion is done using the int() method.
• We take a number from the user and save it n. Inside the function we make a variable num and using the get() method we get the value of n and save it in the num variable.
• We make two variables first and last to store the first and last index number inpython binary search project. Using the len() function we take the length of the list.
• As we have seen in the example, we will perform the same steps using the if else statements till the first index is not equal to the last index which means till the list has more than 1 item. We will be checking if the num is equal to mid, if yes we will print that the number is in the list else not.
• To display the result of the search, we make use of the Label() method to make labels where we specify the desired text that we want to display. To display these labels we use the place() . In the place() function we need to specify the x and y axis.

3. Creating the GUI:

# Create an instance of tkinter frame or window
window=Tk()
# Set the size of the tkinter window
window.geometry("700x350")
window.title("PythonGeeks")#give title to the window
head=Label(window, text="Let's perform Binary Search", font=('Calibri 15'))# a label
head.pack(pady=20)
Label(window, text="Enter number you want to search", font=('Calibri')).pack()# a label

• To create a display window we use the Tk() function. We created a window in python binary search project named window. After making the window we specify the attributes of this window. We have set the size of the window using the geometry() method and title using the title() method.
• We give two labels to display two texts. With labels we can set the font, size, text, foreground colour, background colour etc.To display these labels we use the pack() function. pack() function displays the label on the window.

Entry(window,textvariable=e).pack()
Entry(window,textvariable=n).place(x=280,y=110)#enter a number here
#create a button
Button(window, text="Search", command=binary_search).place(x=320,y=160)

• We create an entry field for the user to enter the number to search. To create this we use the Entry() function. Inside the textvariable, we have given it as n, this means that whatever text will be entered in the entry field will be stored in a variable named n.
• We have also created an Entry field for entering the sorted list. textvariable=e means the elements entered are stored in text variable e.
• To initiate the binary_search function, we create a button using the Button() function. To initiate the binary_search function, we set it as the command inside the Button(). Now whenever we click this button, it will perform the binary_search.

n=tk.IntVar()

• To make sure the entered text is a number we use the IntVar() method.

window.mainloop()#main command

• To display the window that we have created, we use the mainloop(). Without this function, the window will not be displayed.

Python Binary Search Output

You will see the following output when you run the code-

Summary

We have successfully completed the Binary Search Algorithm Project implementation in Python. In this project, we understood the basic concept of GUI using the Tkinter Module and we also understood the working of a binary search algorithm.