This blog post talks about the binary search algorithm and how to implement it in Python. I’m sure you won’t find an easier way out there.
1. Binary Search – An Efficient Search Algorithm
A binary search is an efficient search algorithm for sorted lists. This algorithm is used to find an element from a sorted list of elements. It works by continuously dividing array of elements in half the portion of the list that could contain the element until it is narrowed down to the possible location of having just one. But, one important point to be noted is that in order to find an element from a list by using the Binary search technique, the data collections are expected to be in sorted form.
Binary runs by making O(log n) comparisons. Here ‘n’ refers to the number of elements present in the array. And the ‘O’ is called Big O notation, and ‘log’ refers to the logarithm.
2. Binary Search Algorithm
The binary search algorithm begins execution with the comparison of an element in the middle of the array list with the targeted value. If the element matches the target value, the position of the element in the array is returned.
If the element is more than the target value, the search continues further in the upper half of the array. If the element is greater than the target value the search continues further in the lower half of the array. By continuously performing these iterations, the binary search algorithm eliminates the half portion of the array, every time, when the target value is not found.
Below there is a video which explains the algorithm using some animation:
3. Binary Search Advantages
Binary search is used to solve a wide range of problems, such as identifying the next-largest or next-smallest element in an array relative to the target value, even though it is absent in the array.
4. Binary Search: Python Implementation
Luckily implementing the Binary Search algorithm in Python is very simple. Please see it below.
def binary_search(sorted_list, right_point, left_point, target_number):
# run recursion until this is true
if right_point >= left_point:
mid_point = start_point + (right_point - left_point) // 2
# return element position if it is in the mid_point
if sorted_list[mid_point] == target_number:
return mid_point
# split list. Element is in the left side of the list
elif sorted_list[mid_point] > target_number:
return binary_search(sorted_list, left_point, mid_point - 1, target_number)
# split list. Element is in the right side of the list
else:
return binary_search(sorted_list, mid_point + 1, right_point, target_number)
Below we call the function with a list example from the video above and look for the number “25”.
list_numbers = [1, 3, 4, 5, 13, 20, 25, 40, 42, 44, 53]
target = 25
# Function call
result = binary_search(list_numbers, 0, len(list_numbers) - 1, target)
if result:
print("'{}' was found in the list position {}".format(target, result))
else:
print("'{}' was not found in list. Luckly it took us O(log(n) to look for it".format(target)
# prints '25' was found in the list position 6
More Resources
Here are three of my favorite Python Books in case you want to learn more about it.
- Python Cookbook, Third Edition by David Beazley and Brian K. Jones
- Learning Python, 5th Edition Fifth Edition by Mark Lutz
- Python Pocket Reference: Python In Your Pocket by Mark Lutz
