Binary Search Algorithm

Introduction

The purpose of this article is to explain the Binary Search algorithm and how it works. Then we’ll walk through an example of a binary search in Python so that you can learn how to write one your own.

What is a Binary Search?

A binary search is a search algorithm that finds the position of a target value within a sorted array. It is the most efficient searching algorithm having a run-time complexity of O (log2 N). Binary search is faster than linear search except for small arrays. It is considered a Divide and Conquer algorithm. There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

How it works?

1. The binary search begins by comparing the middle_index of the array with the target_number. If the target_number matches the middle_index, then its position in the array is returned.
2. If it does not match, then the algorithm determines if the target number is greater than or less than the middle_index. Since the array is sorted, it determines if the target_number is in the left (lower) half, or the right (upper) half of the array.
3. The algorithm effectively divided the problem in half. It “rules out” one half of the array that it knows doesn’t contain the target_number.
4. It Repeat the same process, starting at the middle_index on the new half-size array. This process repeats again and again, until the algorithm find the target_number or “rules out” the whole set.

Implement a Binary Search in Python

Let’s take a look at how to implement a binary search using Python. The pseudo-code below will help explain the steps taken for each line of code.

Pseudocode

1. Define low_index and middle_index.
2. Start while loop.
3. Define middle_index.
4. If target_number equals middle_index, then return True.
5. If target_number is less than middle_index then high_index becomes middle_index - 1,
6. If target_number is greater than middle_index then low_index becomes middle_index + 1,
7. If NO target_number, then return False.

Code

def binary_search(lst, target_number):
    """Binary Search Algorithm"""
    # 1. Define low_index & high_index:
    low_index = 0
    high_index = len(lst) - 1

    # 2. Start while loop:
    while low_index <= high_index:
        # 3. Define middle_index:
        middle_index = (low_index + high_index) // 2
        # 4. If target_number == middle_index, then return True:
        if target_number == lst[middle_index]:
            return True
        # 5. If target_number is less than middle_index,
        # then high_index becomes middle_index - 1:
        elif target_number < lst[middle_index]:
            high_index = middle_index - 1
        else:
            # 6. If target_number is greater than middle_index,
            # then the low_index-index becomes middle_index:
            low_index = middle_index + 1
    # 7. If No target_number, then return False:
    return False

Conclusion

This article discussed how the Binary Search algorithm works and how to implement one using python. Hopefully you have a better understanding on how the algorithm works, and can write your own variation. If you found this article helpful or have any questions, please leave a comment.