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”
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
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
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 ! :)
