Binary Search in Python with Examples

The binary search in python is a technique to search elements in a given data set. A binary search is faster than a linear search. However, the binary search’s time complexity is Theta(log n).

But the binary search has one disadvantage. The data set should be in a sorted format. If the data is not in the sorted format, then the binary search will not give output.

It needs a data sorted format because the search element is compared with the middle element of a data set. 

If the search element is less than the middle element, then the searching will take place on the data set’s left side.

If the search element is greater than the middle element, then the searching will take place on the data set’s right side.

If no data found, it will return a search element not found message. 

The binary search algorithm in python

1. Accept data set from the user.
2. Accept the search element from the user.
3. Find the middle element of the data set.
4. Compare search element with the middle element
5. If the search element is less than the middle element, then search the search element on the left side of the data set.
6. If the search element is greater than the middle element, search the search element on the data set’s right side.
7. If data not found, then return false.

How do binary search works?

The binary search in python uses comparison techniques. For numerical data, it directly compares the middle element and searches element. As we all know, python uses a Unicode system so that the comparison is based on the Unicode system only. In the case of characters data set. Alphabetical order is considered. The function will find the middle character of the data set, and if the search element’s character is less than the middle character, it will search the search element on the left side. If the search element’s character is greater than the middle character, it will search the search element on the right side.

Examples of Binary search program in python

We can implement a binary search in python using two ways. The first is iterative and the second is recursive. Let’s see one by one.

1. Binary search in python program using loops.

Accept a data set from the user. While accepting it, make sure that no spaces in between the data. We are storing the entered data in the list. Accept the data in a sorted format and pass it to the function. Use loop for iterate data set. If the element is found in the data set, the function will return the index of the search element. If not, then it will return -1.

Example

def binarysearch(arr, x):
   lowerlimit = 0
   upperlimit = 0
   upperlimit = len(arr) - 1

   while lowerlimit <= upperlimit:
       mid = (upperlimit + lowerlimit) // 2
       if arr[mid] < x:
           lowerlimit = mid + 1

       elif arr[mid] > x:
           upperlimit = mid - 1

       else:
           return mid

   return -1

data = list(input("Enter data: ")) #enter data without using space because we are using list it will store single digit or single character at a time.
print("Entered data is:",data)
key = input("Enter key element")
print("Entered key is:",key)
result = binarysearch(data, key)

if result != -1:
   print("Element is present at index", str(result))
else:
   print("Element is not present in array")

Output

Enter data: 123456789
Entered data is: ['1', '2', '3', '4', '5', '6', '7', '8', '9']
Enter key element4
Entered key is: 4
Element is present at index 3

2. Binary search in python program using a recursive function call.

In this program, we use a recursive function to get an appropriate output. Accept data from the user and pass it to the function. If the data is found in the data set, it will return the index of the search element. Otherwise, it will return -1.

Example

def binarysearch(arr, lowerbound, upperbound, x):

   if upperbound >= lowerbound:

       mid = (upperbound + lowerbound) // 2

       if arr[mid] == x:
           return mid

       elif arr[mid] > x:
           return binarysearch(arr, lowerbound, mid - 1, x)#recursive call to the function

       else:
           return binarysearch(arr, mid + 1, upperbound, x)#recursive call to the function

   else:
       return -1

data = list(input("Enter data")) #enter data without using space because we are using list it will store single digit or single character at a time.
print("Entered data is:",data)
key = input("Enter key element")
print("Entered key is:",key)
result = binarysearch(data, 0, len(data),key)

if result != -1:
   print("Element is present at index", str(result))
else:
   print("Element is not present in array")

Output

Enter data: abcdefghijk
Entered data is: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
Enter key elementk
Entered key is: k
Element is present at index 10