Let's start talking about the efficiency of this algorithm with a new example.
Here we have an array with eight elements and we're going to try and
find the number ten.
Okay, so we'll want to start in the middle.
This problem is a little bit weird because there's an even number of
elements in this array.
So we could either start with four or five really.
When you're designing your algorithm, you need to decide from the start
whether you're going to err on the lower side or
the higher side when you hit this weird case of having no real middle.
I'm going to go ahead and err on the lower side and
start with the number four.
Just like before, we'll check whether our number is bigger or
smaller than the one in the middle.
And since our number is bigger,
now we only need to look at the second half of the array.
Again, we have an even number of elements in our array, so
we're going to pick the number on the left of the middle and start from there.
Okay, since ten is greater than six, yet
again we get to cut our array in half and deal with just the top.
Yet again we have an even number of elements, so
we're going to err on the lower side and check there first.
Since ten is greater than our middle element seven,
we're left with just the last element now.
And now that we've checked the highest element in the array and our number is
still bigger than it, we know that this number doesn't exist and we can move on.
Since the time efficiency is really just the number of steps you're going to
need, keeping track of each iteration is going to help us figure it out.
In the past, we had to step through every single element,
but here we're cutting the array in half and only considering some elements.
So the efficiency isn't going to end up being as big as O(n).
I've created a table so we can take a good look at
the array size versus the number of iterations of our algorithm.
As we just saw, we had to go through our algorithm four times for
an array size of eight.
Again, we're talking about worst case here.
I could have tried to put a number in between all of these places and
on the outsides to figure out what the worst case was.
Just to save your time, I did that before recording this video.
In the process I also discovered a trick here.
If you want to make sure you're checking for the worst case,
you can pick an element that's bigger than anything else in the array.
And when you hit this weird middle case, always favor the lower side.
You should prove this to yourself so you know that it works, but
just trust me on it for now.
Okay, so for an array size of eight, we have worst case for iterations.
We can take the results from the first example too.
There it took us three steps to find something in an array of seven.
Hm, let's start thinking about different array sizes now.
If you had an array size of one and you were looking for an element, say 30,
it would always only take you one step to see whether that element was in your
array or not.
Great, that means we can add one to our table.
Let's say we have an array with two elements in it and we're looking for
this number, 23.
Again, I'm taking advantage of that trick.
I picked a number bigger than the ones that were in the array.
And when I have that weird case, I'm always going to favor the lower side.
And when my array has an even number of elements,
I'm going to pick the number that's on the left of the middle.
Since 23 is greater than 18, I can check 21 now.
In just two steps I have my answer, that 23 doesn't exist in this array.
Great, we can add two to the table now.
In the interest of time, I'm not going to go through all of these examples.
You should definitely do them yourself though to prove that
these results are true.
Okay, we're starting to get a picture of our efficiency here.
I notice that four is half of eight, so
maybe our efficiency looks something like this.
Again, keep in mind that I'm approximating here.
Instead of counting the number of overall steps in the algorithm,
I'm just counting the number of times I'll need to run the algorithm,
in this case four when my n is eight.
Actually I don't know that this is true since half of two isn't two,
and half of one isn't one.
That's too bad.
I really feel like two should go in this efficiency somewhere
since I have to cut the array in half every single time I run the algorithm.
Let me think about exactly what that means for a second.
If I cut the array in half every time I go through an iteration,
that means every time I double the number of elements,
I need to do an extra iteration.
Actually, now that I think about it,
that actually looks true with the results of my table.
Every time my array doubles in size,
it takes an extra iteration of the algorithm to get through it.
Actually when I represent these as exponents, I notice that the power
on top of the two is always one more than the number of iterations it takes.
So maybe my efficiency looks more like this.
The number of overall iterations is going to increase every time
the exponent on the power of two increases, and
of course it's only off by one.
How do I get some number or expression that represents this,
the power of two exponent?
So this is what I'm starting with, the number of elements in my array, and
I want to end up with this number, the exponent.
Well, I remember some weird math that I used to do a long time ago.
There was this thing called a logarithm that let me express
this kind of function in a different way.
Instead of saying this, I could say log base 2 of 8 = 3, and
it means the same thing.
Okay, so this looks a little bit nicer.
I want to make a point to note that you don't need to know a ton about how
logarithms work to understand this.
If you just understand the equations I showed you before, you should be fine.
So we could actually use another approximation to make this
look even nicer.
As I mentioned before, adding a constant or
adding one doesn't really change my efficiency very much.
Also, I don't really need to say that this is log base 2.
In computer science it's actually pretty safe to assume that your logs are in
base 2.
We often do things like cut arrays in half or use binary.
So our logs are normally going to be in base 2 instead of the typical base 10.
So this is the efficiency that we end up with.
A little later on we'll have some more tools.
So it'll be easier for
me to show you visually why this efficiency makes sense.
There's one thing I want to make very clear to you all right now.
When I was learning about efficiency,
it often seemed like people could just jump to this conclusion.
They could just look at the original problem and say,
of course this is log n.
However, after years of being a developer,
I learned that that really wasn't the case.
I found that there are three main ways that people can get to this efficiency.
One of them is just by knowing what binary search is,
having seen it before, and being able to just memorize the efficiency and
spit it out when you see it again.
I highly recommend you just memorize the efficiency of basic algorithms for
your interviews.
It'll make you seem really smart if you can just spit out the efficiency
from the start.
However, if you're presented with a new problem and
you don't know the efficiency of the algorithm already,
you need to be able to solve it on your own.
One way you can do that is with proofs.
I personally don't like proofs and have never used them in an interview or
seen other people use them in interviews.
If you want to learn how to make proofs, you can look it up online and
go read research papers and see other people step through that.
However, my goal is to teach you the practical approach to this.
When you haven't seen the algorithm already, and
you don't have time to whip up a proof out of nowhere, making a results table
like this is actually one of the best things you can do.
Creating a results table helps you notice patterns and
helps you start thinking about efficiency in terms of array size
versus the number of iterations of your algorithm.
When I first started learning about efficiency,
I needed tables like this to see those patterns.
However, after using tables for a while,
I started to be able to see the patterns on my own without them.
Now when I interview,
I know what types of patterns are common like changes in the powers of two.
And now I solve problems way quicker and
there are very few problems that I can't at least approach and try to solve.
The worst thing you can do in an interview is say I've never seen this
algorithm before or I don't know how to write a proof for it.
If you're down on your luck and you really don't know what the answer is,
please make a results table and try to figure it out.
Your commitment to solving the problem is really going to impress your
interviewer.