# Decrypting Binary Search

--

/* Ever wondered how websites like Facebook search your name query that you make in milliseconds, it all comes down to the very basics of computer science.

Binary Search is an algorithm that is basic but one of the most effective that has been easing the lives of computer scientists and programmers. Before we head on to the mechanism of this problem solving technique, let us know how it differentiates from the normal problem solving technique.

You want to make a simple search in which box has the cupcake among the hundred cupcakes and your friend will be telling you if your selection is high or low in respective to the chosen box. The dumbest way is to start from first box itself and go on till the last one because you are not able to extract the advantage that your friend will be guiding you in your search (whom we can refer to as the computer in technical world).

Now comes the main hero of the show, Suppose the cupcake was in the box number 57, the simplest technique is to start from the box number. 50. I will bifurcate the next steps to help you understand binary search better.

**Pass 1:**

You open Box Number. 50 and your friends comes out to say: TOO LOW ALIM!

You have the hint that the box is in between 50 and 100 and you go on to eliminate first 50 boxes.

**Pass 2:**

You open the mean of first and last box you are left with i.e. Box Number. 75 and your friend says its way too HIGH!

Easy until now, the word HIGH tells you that you must eliminate anything that is over 75. We have Boxes in between 50 and 75.

**Pass 3:**

You divide again and your result, 63 is once again above the par of the required box. Don’t get frustrated as we are just at the final door to solve it.

Summing up 50 and 63 and dividing it and incrementing one because we do not want to ignore value lost in diving odd number by 2.

**Pass 4:**

We get 57 and that the friend shouted. YES!!. All it took us was 4 passes to find the cupcake instead of going through tedious 57 boxes. Wasn’t that easy as a muffin.

The time complexity if Binary search is O(log n) which is way better than what we get in Linear Search O(n) but do not forget that Binary search can work only on sorted data which is the reason they are so effective with dictionaries. */