Binary Search Using Python

Introduction

In this blog, we will discuss the Binary Search technique. In Linear Search, first, we have to enter the elements in the array and then, we have to iterate the array for finding a particular value. Here, the array can either be in a sorted or an unsorted manner. If the particular searching element is found, then we have to return the element and position from the array. If not, we have to print the message like "Element not found in the array".

In a Binary Search technique, first, we have to enter the elements into the array and then, we have to sort the array in ascending or descending order based on our convenience. Then, we have to set the array's lower and upper bound. With those upper and lower bounds, we have to find the mid-value and iterate the array if the mid-value is greater or smaller than the searching element.

Then, we have to divide the array elements again. Now, we have to search for the lower bound, upper bound and mid value and do it recursively until the searching element is found. If the particular searching element is found, then we have to return the element and position from the array. If not, we have to print the message like "Element not found in the array". So, let's get started.

Note

For different Python IDEs, we have different ways to execute, however, the result remains the same. For those who are using Visual Studio IDE for Python, the process will be something as shown below.

Step 1

Open your Visual Studio 2017 Community Edition.
Go to File -> New -> Project. Then, a new window will appear.
Under Installed, select Python.
On the right side of the window, select Python Application. Then, give the name of the project and save it on your required location.
Click OK.

Step 2

Now, open a .py file and write the following code in the file.

Python Code

def BinarySearch(list,n):
l = 0
h = len(list)-1
found = 0
while i <= h:
mid = (l + h) // 2
if list[mid] == n:
print("Element {} found at position {}".format(n,mid+1))
found = 1
return True
if list[mid] > n:
h = mid - 1
if list[mid] < n:
l = mid + 1
if found !=1:
print("Searching element {} not found in the array list".format(n))
return
list = []
size = int(input("Enter the size of the array: "))
for i in range(size):
x = int(input("Enter the element at {} position in the array: ".format(i+1)))
list.append(x)
list.sort()
print("Entered array elements are: ")
for lists in list:
print(lists,end="\t")
se = int(input("\nEnter the array element to be searched: "))
BinarySearch(list, se)

We are not using an "array" library because we don't have a sort() function in the "array" library.

First, we are creating a list then, we enter the elements and then, sort the list. Next, we enter the searching element in the list. Later, we call the BinarySearch() function which has two parameters. The first parameter is accepting the list and the second parameter is accepting the searching element. Then, we assign the lower and upper bound and we initialize the variable called "found" which will be first assigned as 0. Then, if the searching element is found, we set it to 1.

Again, we calculate the mid-value and based on the values, the array will be divided and searched until the searching element is found. If the searching element is found, it returns the searching element and position in the list. Else, it will display the message.

Outputs

Conclusion

Now, we have successfully implemented the Binary Search program to sort and find the particular element.

2 Comments

Join the conversation! Your thoughts help the community grow.

Gaurav Gahlot7y ago
Hi Kartik! I think the output images are incorrect. Please fix them as soon as possible. Also, I would recommend to clean up your code a bit and mind the indentation. Since this is a good topic and many readers would want to use the code, I would suggest to add appropriate comments.
- Kartik Pawar7y ago
  Gaurav i also found that the outputs are to be corrected and i will make the code indentation also.