Binary Search — Algorithms

In the Last blog post we went through the idea of Algorithms or in other terms particular set of commands or codes followed in order to complete a task. There are many Algorithms that can be used to solve or complete the exact same task with the exact same results.

But what differs in these Algorithms is the time or the number of attempts they require to complete the task. Which is in most cases the most important thing , because we schedule almost all our tasks based on deadlines.

A Simple Task

Imagine a situation where we go through the phone book to find a number of a particular company. A typical phone directory would have an order in placing the numbers. Commonly the numbers will be sorted according to alphabetical order of the first letter of each name of the owner of the phone number.

And we are given the task to find the number of “Jimbly” . An insurance company. So we can complete this task by using different methods or the precise term here, different algorithms.

We can start the search from the beginning of the directory and go through each and every name we come across and check whether that name equals with what we are searching for. This method is known as “Linear Search”

Linear search algorithm

What is Binary Search?

But there is a much faster way to do this. In fact without knowing the actual name for this method, we have used it in our day to day life. This method is known as “Binary search” , and this is how it works.

Here we know the phone directory is sorted according to alphabetical order . And if we know the alphabet , we all know that letter “J” is located towards the middle of the alphabet. So Instead of following the Linear search mentioned about i.e. going through each name starting from A.

We can directly jump to a middle page and and cut off the search time for half of the directory . And this Method is known as Binary Search.

A Binary Search Example

Super Mario Using Binary search algorithm

If you have ever played the game super Mario, You might have come across one of those levels were we our objective is to find the mushroom which is hidden in one of the boxes. And the only way to know whether that box carries a mushroom is to jump on to that box.

So as depicted in the diagram above instead of starting from the first box, Mario directly jumps onto the middle box. And the boxes he jumped over got revealed. and he is left out with half of the boxes to search for.

And Again he jumps to the middle of the remaining set of boxes which again cuts out the number of boxes to be searched by half. And he continues this process repeatedly until he is left with just one box.

Definition of Binary Search

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

This method as we went through in the examples , cuts out the attempts and the time to find the required target by half in each move we make.

When we use the Linear search, if the directory we had to go through to find the name “Jimbly” had 10000 names. We have to go through each of those 10000 names in order to find the name we need in the worst case scenario, i.e. “Jimbly” Being the last name of the directory.

But when Binary search is used it only takes around 14 attempts to find the target. Since each attempt will cut out the search load by half.

10000 → 5000 →2500 →1250 →625 →……. and so on

another example for binary search

So Binary search can be used instead of linear search everywhere?

Answer is NO!. The basic requirement to use binary search is that the set of data we are going through has to be sorted , like the definition itself says.

Binary search cannot be used for random unsorted set of values. But there are ways used to make an unsorted list into a sorted one in order to use Binary search. Which we will discuss in future writings ,

Till then Happy coding ! :)

--

--

--

Undergraduate of Software Engineering University of Westminster UK.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Legacy Code: definition, recommendations & books

Boostnote | Boost your happiness, productivity and creativity.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Seyed Akeel

Seyed Akeel

Undergraduate of Software Engineering University of Westminster UK.

More from Medium

Arrays — Understanding the random access

Leetcode Q482. License Key Formatting (Q410)

Detail of binary search

Connect Ropes(code and explanation)