So let's end going back to these same thought questions.

So, we said before, in a linear search if we get unlucky

we're gonna have to look through every single element in our array and

if there are a lot of elements in our array, like there are a lot of

words in the dictionary, that can be a very, very slow, cumbersome process.

So, binary search is going to improve on that a lot.

So, you notice when we were tracing through the algorithm, and

when I was looking through the dictionary, that I could eliminate essentially half of

the remaining choices, without even looking at them.

Every step through the loop, that was great.

And if I do this process repeatedly, what I'm doing is I'm dividing the number of

things I have to look at in half every time.

So I divide my original numbers in half, I have half as many.

I divide that in half, half as many again.

And half and half and

half and half until I get down to just a single element that I'm looking at.

And, it turns that the way the function that expresses,

that half-half-half-half function is the logarithm.

It's the logarithm base two.

So, if I compare the function that represents the number of elements that I

have to look at in linear search which is just equal to n,

the number of elements that I have in my ray to that log base to n function.

I can see that these two functions behave very differently.

So when my n is fairly small, say two, 32, 1024 my log is also quite small.

But you know the two values aren't horribly different.

But as n gets very, very large,

you can see that a huge difference emerges between these two values.

N grows, and it can get pretty darn big.

So it can get into the billions.

There are about 7.2, 7.4,

depending on when you're watching this video, billion people on the planet.