Python Program For Binary Search (With Code)

In this tutorial, you will learn about the python program for binary search.

In the world of programming, searching for specific elements in a collection of data is a common task.

One of the most efficient search algorithms is the binary search algorithm.

In this article, we will delve into the intricacies of the binary search algorithm and provide a comprehensive guide on how to implement a Python program for binary search.

What is Binary Search?

Binary search is a search algorithm that finds the position of a target value within a sorted collection of elements.

The algorithm compares the target value with the middle element of the collection.

If the target value is equal to the middle element, the search is successful.

Otherwise, the algorithm narrows down the search range by half and continues the process in the appropriate half of the collection.

This approach significantly reduces the search space with each iteration, resulting in a time complexity of O(log n), where n is the size of the collection.

To implement the binary search algorithm in Python, we need a sorted collection of elements and a target value to search for.

Let’s start by writing a Python function for binary search.

Python Program For Binary Search

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        
        if arr[mid] == target:
            return mid
        
        elif arr[mid] < target:
            low = mid + 1
        
        else:
            high = mid - 1
    
    return -1

You can run this code on our free Online Python Compiler.

Let’s break down the implementation.

The binary_search() function takes two parameters: arr, which represents the sorted collection of elements, and target, which is the value we want to find.

We initialize low and high variables to keep track of the search range.

The while loop continues until low becomes greater than high, indicating that the target value is not present in the collection.

Inside the loop, we calculate the mid index as the average of low and high.

We compare the value at the mid index with the target value.

If they are equal, we have found the target, and we return the index.

If the value at mid is less than the target, we update low to mid + 1 to search in the right half of the collection.

Otherwise, we update high to mid - 1 to search in the left half of the collection.

If the loop exits without finding the target value, we return -1 to indicate that the target is not present in the collection.

Now that we have the Python program for binary search, let’s explore its various aspects and see it in action.

Example 1: Searching an Integer in a Sorted List

Let’s consider a scenario where we have a sorted list of integers and we want to find the index of a specific integer using binary search.

Here’s an example code snippet:

Python Program for Binary Search

numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target = 14

index = binary_search(numbers, target)
if index != -1:
    print(f"The target value {target} is found at index {index}.")
else:
    print("The target value is not present in the list.")

Output

In this example, we have a sorted list of numbers, and we want to find the index of the number 14 using the binary search algorithm.

The program successfully locates the target value at index 6 and displays the appropriate message.

Example 2: Searching a String in a Sorted Array

Binary search is not limited to searching for integers.

You can also use it to search for strings in a sorted array.

Let’s consider an example.

Python Program for Binary Search

fruits = ["apple", "banana", "cherry", "grape", "mango", "orange", "strawberry"]
target = "mango"

index = binary_search(fruits, target)
if index != -1:
    print(f"The target value '{target}' is found at index {index}.")
else:
    print("The target value is not present in the array.")

Output

In this example, we have a sorted array of fruits, and we want to find the index of the fruit “mango” using the binary search algorithm.

The program successfully locates the target value at index 4 and displays the appropriate message.

Q: What is the time complexity of the binary search algorithm?

The binary search algorithm has a time complexity of O(log n), where n is the size of the collection.

This makes it highly efficient for searching large sorted collections.

Q: Can I apply binary search to unsorted collections?

No, you can’t use binary search for unsorted collections.

If the collection is unsorted, the algorithm will not produce correct results.

Q: Is binary search limited to numeric values?

No, you can apply binary search to any type of data.

You can use it to search for integers, floating-point numbers, strings, and other comparable data types.

Q: What happens if the target value is not present in the collection?

If the target value is not present in the collection, the binary search algorithm will eventually narrow down the search range until the low index becomes greater than the high index.

At that point, the algorithm will exit the loop and return -1 to indicate that the target value is not found.

Q: Is it necessary to use a sorted collection for binary search?

Yes, binary search requires a sorted collection.

If the collection is unsorted, the algorithm will not work correctly.

Q: Can binary search be used on linked lists?

Binary search is not suitable for linked lists because accessing elements in a linked list takes linear time, resulting in an overall time complexity of O(n), which defeats the purpose of using binary search.

It is more efficient to use binary search on arrays or other random access data structures.

In conclusion, the binary search algorithm is a powerful and efficient search algorithm for sorted collections.

By dividing the search space in half with each iteration, it quickly narrows down the possible locations of the target value.

We have covered the implementation of a Python program for binary search and explored its usage with examples.

We have also addressed common questions and provided answers to enhance your understanding of this algorithm.

Incorporating the binary search algorithm in your Python programs will greatly improve their search capabilities.