Binary Search in Python

Binary Search in Python

Introduction

Searching is a fundamental operation in computer science, and binary search is one of the most efficient algorithms for finding an element in a sorted list. Suppose we have a list of a thousand elements, and we need to determine the index position of a specific element—binary search allows us to find it quickly.

Among various searching algorithms, binary search stands out due to its efficiency and widespread use in real-world applications. However, the list must be sorted before applying the binary search algorithm. The items must be sorted first if they aren’t already.

Let’s explore the concept of binary search in detail.

Complete Python Course with Advance topics:-Click here

Concept of Binary Search

The divide and conquer strategy is used in binary search. There are two ways to implement it:

1. Recursive Method
2. Iterative Method

Until the element is located, the recursive approach calls a function repeatedly. In contrast, the iterative method uses a loop to iterate through the list until the element is located.

Binary search is much faster than linear search since it doesn’t check each index sequentially. Instead, it narrows the search space by half in each step, making it significantly more efficient.

Steps to Implement Binary Search

Let’s assume we have a sorted list and we want to find the index position of 45:

list1 = [12, 24, 32, 39, 45, 50, 54]
n = 45

We set two pointers:

• low → Points to the smallest index
• high → Points to the highest index

Then, we calculate the middle index:

mid = (low + high) // 2

Here, low = 0 and high = 6:

mid = (0 + 6) // 2
mid = 3

We compare list1[mid] with n. If it matches, we return mid. Otherwise:

• If n is greater than list1[mid], we search in the right half.
• If n is smaller than list1[mid], we search in the left half.

This process repeats until we find the element or determine that it is not present in the list.

Implementing Binary Search in Python

Iterative Method

Below is the Python implementation using an iterative approach:

# Iterative Binary Search in Python
def binary_search(list1, n):  
    low = 0  
    high = len(list1) - 1  
    
    while low <= high:  
        mid = (low + high) // 2  
        
        # If element is present at mid
        if list1[mid] < n:  
            low = mid + 1  
        elif list1[mid] > n:  
            high = mid - 1  
        else:  
            return mid  
    return -1  

# Example usage:
list1 = [12, 24, 32, 39, 45, 50, 54]  
n = 45  
result = binary_search(list1, n)  

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

Output:

Element is present at index 4

Explanation:

• A sorted list and a target number are passed to the binary_search() function.
• The search space is tracked by two pointers, one high and one low.
• Until low exceeds high, the while loop keeps going.
• We return the index of the middle element if it matches n.
• We update low if n exceeds the middle element.
• We update high if n is less than the middle element.
• We return -1 if n cannot be found.

Recursive Binary Search

Recursion can also be used to implement binary search:

# Recursive Binary Search in Python
def binary_search_recursive(list1, low, high, n):
    if low <= high:
        mid = (low + high) // 2
        
        if list1[mid] == n:
            return mid
        elif list1[mid] > n:
            return binary_search_recursive(list1, low, mid - 1, n)
        else:
            return binary_search_recursive(list1, mid + 1, high, n)
    else:
        return -1

# Example usage:
list1 = [12, 24, 32, 39, 45, 50, 54]
n = 32
res = binary_search_recursive(list1, 0, len(list1) - 1, n)

if res != -1:
    print("Element is present at index", res)
else:
    print("Element is not present in list1")

Output:

Element is present at index 2

Explanation:

• The recursive function keeps calling itself with updated values of low and high.
• If the middle value equals n, the search ends.
• If n is less than the middle value, the function is called recursively for the left half.
• If n is greater than the middle value, the function is called recursively for the right half.
• If low exceeds high, the function returns -1, indicating the element is not found.

Complexity Analysis

Why is Binary Search Efficient?

• Unlike linear search (O(n)), binary search reduces the search space by half at each step.
• This makes it ideal for large datasets.
• Works best on sorted lists.

Download New Real Time Projects :-Click here
Complete Advance AI topics:- CLICK HERE

Conclusion

Finding an element in a sorted list can be done quickly and effectively with binary search. It eliminates unnecessary comparisons, making it much faster than linear search. We explored both iterative and recursive implementations in Python.

By understanding and implementing binary search, programmers can optimize search operations, making their applications run faster and more efficiently.

This tutorial was brought to you by UpdateGadh, your go-to platform for the latest programming insights and tutorials.

binary search in python with example
binary search in python using for loop
binary search in python inbuilt
binary search in python using list
binary search in c
binary search in python without function
binary search in python w3schools
Binary Search in Python algorithm
Binary Search in Python