A Simplified Interpretation of Binary Search

This blog post is a continuation of a series of blog posts about Algorithms, as it has been a hard concept for me to grasp as a programmer. Feel to check out the first blogpost about Algorithms, where I provide an introduction of what Algorithms are and an example of an algorithm and the second blog post about Data Structures, where I explained what are Data Structures and what are some types of Data Structures. Also check out the third blog post about Time Complexity and Space Complexity, which I provide an explanation of Time and Space Complexity. Recently I have written a blog post about Big O Notation.

This blog post I will focus on the Binary Search. I will explain what is the Binary Search, how is Binary Search associated with Algorithms, try to break down the concept of Binary Search step by step and provide an example.

What is Binary Search and how is it associated with Algorithms?

Binary Search is a type of searching algorithm. A searching algorithm means you find an item with a particular value in a sorted sequence. Binary search is a type of searching algorithm which finds an item by repeatedly halving the search space.

Here is a great video by Hackerrank which provides an explanation of Binary Search:

And a visualized image of Binary Search as well:

Binary Search: Steps on how it works:

To find the index of element e with a certain value:

1. Start with an array sorted in descending order.
2. In each step: Pick the middle element of the array m and compare it to e. If element values are equal, then return index of m. If e is greater than m, then e must be in left subarray. If m is greater than e, then e must be in the right subarray.
3. Repeat those steps on new subarray.

Binary Search: An example

Here is an example of writing the Binary Search Algorithm based on the steps I provided earlier. Below I have written a function, which accept the following parameters: an array and a value I want to find. The function returns the index of the found value.

Regarding Time/Space Complexity in Binary Search, since this algorithm splits array in half every time, at most log2N steps are performed. N equals the number of items in sequence.

There are other searching algorithms as well called linear and interpolation search. The performance of searching algorithms varies depending on sequence characteristics (distribution).

Overall binary search is an important concept to understand when it comes to algorithms. Thank you for reading this blog post. In upcoming blog posts of this series, I will go over sorting algorithms.