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?
The binary search begins by comparing the
middle_index
of the array with thetarget_number
. If thetarget_number
matches themiddle_index
, then its position in the array is returned.If it does not match, then the algorithm determines if the
target number
isgreater than
orless than
themiddle_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.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.It Repeat the same process
, starting at themiddle_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
- Define
low_index
andmiddle_index
. - Start while loop.
- Define
middle_index
. - If
target_number
equalsmiddle_index
, then returnTrue
. - If
target_number
is less thanmiddle_index
thenhigh_index
becomesmiddle_index - 1
, - If
target_number
is greater thanmiddle_index
thenlow_index
becomesmiddle_index + 1
, - If
NO target_number
, then returnFalse
.
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
Top comments (0)