Binary Search O(Log N)

Given a sorted array how can we find a number in the most optimal time?

Binary Search is a way where we can divide the problem in half each iteration we go. It's actually one the most easiest and fundamental search algorithm that runs in O(Log N) time.

What the heck is O (Log N)?

First we need to understand what the O in this means. 

In computer science, "O" typically refers to Big O notation, which is used to describe the performance or complexity of an algorithm. Big O notation provides an upper bound on the growth rate of an algorithm's time or space complexity in terms of the input size. It is a way to analyze and compare the efficiency of different algorithms.

For example, if an algorithm has a time complexity of O(n), it means that the running time of the algorithm grows linearly with the size of the input. If an algorithm has a time complexity of O(log n), it means the running time grows logarithmically with the input size.

The "O" in Big O notation stands for "order of," and it is followed by a mathematical expression that describes the upper bound of the algorithm's growth rate.

Great? Great. So what does Log N mean?

Well in terms of N, given an array of elements of size N or in other words given a stash of 16 apples we can say N is 16. 

As for log you will need to understand what the log function means in math; Log is a function to find the exponent of an expression.

Expressed mathematically, x is the logarithm of n to the base b
if b^x = n, in which case one writes x = log b n.

Log 100 in base of 10 is equal to 2, because 10^2 = 100. However since computers work in base 2 we can say that Log 16 in base 2 is equal to 4 because 2^4 = 16. 

Now how does O (Log N) factors into play? Well time complexity is important topic of discussion in computer science because it helps us measure approximately how long our algorithm will take given in Time T. 

Let's further use our apple example; say we want to get the 9th apple out of the 16 apples we have. If we want to get the 9th apple we have to count starting from 1 until we get to 9.

That will take 9 whole iterations to get the 9th apple. Well with binary search, searching is much different.

We start off with a low + high value, our low would be 0, our high will be the size of the array or how much apples we have and our mid will be the average of Low + High. 

Target = 9, Low = 0, High = 16, Mid = (Low + High / 2) = 8

In binary search we know that 8 is not what we're looking for since we have a higher target so we say Low = Mid + 1. 

Low = 9, High = 16, Mid = (9 + 16) / 2 = 12

Why is it 12? Since it's an array we are working with and array indexes are integers; integers truncates after the decimal point leaving only the number before the decimal point essentially it's taking the floor of the number. 

In this case our Target is lower so we say High = Mid.

Low = 9, High = 12, Mid = (9 + 12) / 2 = 10

Target is lower; High = Mid.

Low = 9, High = 10, Mid = (9 + 10) / 2 = 9

Our mid is now equal to our target but guess what? That only took 4 iterations which is why our formula is O (Log N) because Log 16 of base 2 is equal to 4.

So next time you go into the supermarket and you want to find the 9th apple on the shelf just remember this formula so you can look for it in O (Log N) time. Just binary search it 👌🏾