Python Program for Binary Search

In this Python article, we’ll dive into the mechanics of the Binary Search algorithm, then we’ll implement the algorithm in Python.

What is Binary Search in Python

Binary Search is a popular searching algorithm that is highly efficient for searching an element in a sorted list. Its efficiency comes from the fact that with each comparison, it halves the size of the list, thus reducing the search space drastically.

Binary Search in Python

At its core, the Binary Search algorithm follows these steps in Python:

1. Compare the target value to the middle element of the list.
2. If they are not equal, the half in which the target cannot be located is eliminated.
3. Repeat these steps until the target value is found or the remaining list is empty.

This process of elimination makes the Binary Search algorithm very efficient, with a time complexity of O(log n), where n is the number of elements in the list.

Python Program for Binary Search

Now, let’s implement the binary search algorithm in Python. We’ll write a function that takes a sorted list and a target value as input, and returns the index of the target value in the list. If the target value is not in the list, the function will return -1.

Here is the Python code for binary search:

def binary_search(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = sorted_list[mid]
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
    return -1

# test the function
print(binary_search([1, 2, 3, 4, 5], 3))  

• In this Python function, we first initialize two pointers, low and high, to the first and last index of the list, respectively. Then we enter a while loop, which continues as long as low is less than or equal to high.
• In each Python iteration, we calculate the index of the middle element (mid) and the middle element itself (guess).
  • If guess equals the target, we have found the target and return mid.
  • If guess is greater than target, we know that the target must be in the left half of the list, so we adjust high to mid - 1. If guess is less than target, we adjust low to mid + 1.
• If the Python while loop finishes without finding the target, we return -1 to indicate that the target is not in the list.

Output:

Example of Binary Search in Python

Let’s consider an example where we have a sorted list of cities by population in the United States and we want to find the position of a specific city in this list.

Imagine we have a list of the ten most populous cities in the U.S.:

cities = ["New York", "Los Angeles", "Chicago", "Houston", "Phoenix", "Philadelphia", "San Antonio", "San Diego", "Dallas", "San Jose"]

We can use the Python binary search algorithm to find the position of a city in this list. Since the Python binary search algorithm only works with numerical values, we need to convert our city names into numerical IDs (like their index in an alphabetical list of all cities in the U.S.).

For the sake of this example, let’s say that we have converted the city names into these numerical IDs:

city_ids = [5, 4, 1, 2, 8, 7, 9, 6, 3, 10]

Now the list is sorted:

sorted_city_ids = sorted(city_ids)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Now let’s say we want to find the position of San Diego (which has ID 6) in this list. Here is how we could use the binary search algorithm in Python:

def binary_search(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = sorted_list[mid]
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
    return -1

# test the function
print(binary_search(sorted_city_ids, 6)) 

In this case, the Python binary_search function returns 5, which means that San Diego is the 6th most populous city in the sorted list of U.S. cities.

Output:

Conclusion

Binary search is a highly efficient searching algorithm with a time complexity of O(log n). This efficiency is achieved by halving the search space in each iteration, which drastically reduces the number of comparisons that need to be made. The Python code for binary search is simple and elegant, demonstrating the power of algorithmic thinking.

You may like the following Python tutorials:

• Armstrong number in Python
• Python program for bubble sort
• Python program for a diamond pattern
• Add two binary numbers in Python