Python Program for Binary Search

In this post, you will learn how to write a python program for binary search with a detailed explanation and algorithm so let us start from very basic.

What is Binary Search

Binary Search is a searching algorithm to find the position of the specific element present inside a sorted array or list.

• Binary Search is also called a half-interval search.
• It is the fastest searching algorithm with time complexity of O(logn).
• Binary Search is based on a divide & conquer strategy

Algorithm for Binary Search

NOTE: In Binary Search your list should be in sorted order (ascending order).

1. def binarySearch(my_list,x):(where x is an element that we want to find inside a list).
2. Take two-pointers low & high.
3. low points to the first element of the list and high points to the last elements of the list.
4. while low <= high do mid = low + high // 2. (mid gives the position of the middle element of a list)
5. if x == my_list[mid] then return mid (it gives position of x).
6. elif x > my_list[mid] then do low = mid + 1
7. else do high = mid -1
8. Exit from the while-loop.
9. return -1 (this indicates that x is not present in the list)

Example:

From the above example and algorithm, we understood how to implement a binary search program in python but before writing a program few programming concepts you have to know.

1. while loop
2. if-elif-else &
3. function in python.

Source Code

def binarySearch(my_list,x):
    low = 0
    high = len(my_list) -1 

    while low <= high:   
        mid = (low+high)//2   # find mid

        if x == my_list[mid]:  
            return mid

        elif x > my_list[mid]: 
            low = mid+1   

        else:
            high = mid-1
    
    return -1

list1 = [1,2,3,4,6]

print(f"Element is present at position {binarySearch(list1,6)}")  #gives index position

Output

Element is present at position 4

Python Program for Binary Search using Recursion

Before writing a program you should about:

1. if-elif-else &
2. recursive function in python

Source Code

def binarySearch(my_list,x,low,high):
    if low <= high:
        mid = (low+high)//2   # find mid

        if x == my_list[mid]:  
            return mid

        elif x > my_list[mid]: 
            return binarySearch(my_list,x,mid+1,high)  

        else:
            return binarySearch(my_list,x,low,mid-1)
    else:
        return -1



list1 = [1,2,3,4,6]
x = 6
low = 0
high = len(list1) -1

print(f"Element is present at position {binarySearch(list1,x,low,high)}")

Output

Element is present at position 4

Related Programs:

1. Linear Search in Python (with Source code)
2. Matrix multiplication in Python with user input
3. How to Reverse a list using recursion in Python
4. Palindrome in Python using recursion
5. Python program to find Factorial of N numbers