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.
      
    Binary Search Using Python
     
Step 2
 
Now, open a .py file and write the following code in the file.
 
Python Code
  1. def BinarySearch(list,n):    
  2.    l = 0    
  3.    h = len(list)-1    
  4.    found = 0    
  5.    while i <= h:    
  6.       mid = (l + h) // 2   
  7.    
  8.       if list[mid] == n:    
  9.          print("Element {} found at position {}".format(n,mid+1))    
  10.          found = 1    
  11.       return True     
  12.       if list[mid] > n:    
  13.          h = mid - 1    
  14.       if list[mid] < n:    
  15.          l = mid + 1    
  16.    if found !=1:    
  17.       print("Searching element {} not found in the array list".format(n))    
  18.        
  19.    return    
  20.        
  21. list = []    
  22. size = int(input("Enter the size of the array: "))    
  23.        
  24. for i in range(size):    
  25.      x = int(input("Enter the element at {} position in the array: ".format(i+1)))    
  26.      list.append(x)    
  27.       
  28. list.sort()    
  29. print("Entered array elements are: ")    
  30. for lists in list:    
  31.     print(lists,end="\t")    
  32.      
  33. se = int(input("\nEnter the array element to be searched: "))    
  34. BinarySearch(list, se)   
image1
 
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
 
image2
 
image3
 

Conclusion

 
Now, we have successfully implemented the Binary Search program to sort and find the particular element.
Next Recommended Reading Simple Stopwatch Using Python