In this article, you will learn how the Binary Search algorithm works behind the scenes and how you can implement it in Python.
In particular, you will learn:
- How the algorithm works behind the scenes to find a target element.
- How its Python implementation works line by line.
- Why it is a very efficient algorithm compared to Linear Search.
- Its advantages and requirements.
- Let's begin! ✨
📌 Intro to Binary Search
This algorithm is used to find an element in an ordered sequence (for example: a list, tuple, or string).
Requirements
To apply the Binary Search algorithm to a sequence, the sequence already has to be sorted in ascending order. Otherwise, the algorithm will not find the correct answer. If it does, it will be by pure coincidence.
💡 Tip: You can sort the sequence before applying Binary Search with a sorting algorithm that meets your needs.
Input and Output
- The algorithm (implemented as a function) needs this data:
- An ordered sequence of elements (for example: list, tuple, string).
- The target element that we are searching for.
- It returns the index of the element that you are looking for if it's found. If the element is not found, -1 is returned.
Efficiency
It is very efficient compared to Linear Search (searching for an element one by one, starting from the first one) because we are able to "discard" half of the list on every step.
Source Code
def binary_search(data, elem):
low = 0
high = len(data) - 1
while low <= high:
middle = (low + high)//2
if data[middle] == elem:
return middle
elif data[middle] > elem:
high = middle - 1
else:
low = middle + 1
return -1