## DEV Community π©βπ»π¨βπ» is a community of 963,673 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Seraphβ776

Posted on

# Python: 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 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`.
``````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
``````