Binary Search in Python
Introduction
In this article, we’ll be diving into the idea behind and Python implementation of Binary Search.
Binary Search is an efficient search algorithm that works on sorted arrays. It’s often used as one of the first examples of algorithms that run in logarithmic time (O(logn)) because of its intuitive behavior, and is a fundamental algorithm in Computer Science.
Binary Search – Example
Binary Search works on a divide-and-conquer approach and relies on the fact that the array is sorted to eliminate half of possible candidates in each iteration. More specifically, it compares the middle element of the sorted array to the element it’s searching for in order to decide where to continue the search.
If the target element is larger than the middle element – it can’t be located in the first half of the collection so it’s discarded. The same goes the other way around.
Note: If the array has an even number of elements, it doesn’t matter which of the two “middle” elements we use to begin with.
Let’s look at an example quickly before we continue to explain how binary search works:
As we can see,