Python: Binary Search Algorithm 🔎
Tags: python, programming, algorithms, tutorial
Published: 2022-08-21 11:41:32

## 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 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.

3. `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`,<br>
6. If `target_number` is greater than `middle_index`
   then `low_index` becomes `middle_index  + 1`,<br>
7. If `NO target_number`, then return `False`.


```python
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.

---
Code available at [GitHub](https://github.com/seraph776/DevCommunity/tree/main/BinarySearchAlgorithm)