Binary Search in Python

This post demonstrates how to implement binary search in python.

Photo by Markus Winkler on Unsplash

Introduction

Binary Search is an algorithm for searching a specific value in an ordered collection. It can be used to search for either an index or an element in the collection. The algorithms divide the search space in two after every comparison.

Algorithm

Precondition: The collection must be sorted. If the collection is unordered, we need to sort it first before applying the binary search.

Steps

1. Initialize left and right to the index of left most and right most items in the given array to be searched.
2. Get the middle element between the left and right index of the array.
3. compare item with the middle element.
4. If item matches with the middle element, return the middle index.
5. Else if item is greater than the middle element, then item lies after the middle element on the right half of the array.
6. If item is smaller, the item lies before the middle element towards the left half of the array.
7. Repeat steps 1 to 5 until left has gone past the right.
8. Return False or -1 (as error code) to indicate item not found.

The algorithm takes advantage of the ordering of the elements in the sorted array and ignores half of the element after each comparison.

python code for the binary search

Conclusion

The binary search algorithm has a time complexity of 𝑂(𝑙𝑜𝑔𝑛) and space complexity of 𝑂(1)