So now that we have had a solid introduction to algorithm analysis, it's time for us to expose ourselves
to some other, more interesting problems.
And in this particular lecture, one I'm going to be looking at is binary search algorithm.
So if some of you have not heard of binary search, that is totally fine.
I'm going to go over the algorithm both in theory and the code implementation, of course, before I
get into the analysis part.
If you had her have heard of binary search or even maybe used it, this will just be a recap for you.
And if you like, you can skip ahead to the portion in which we do the analysis.
And I'm going to also be looking at the recursive implementation of this.
Some of you who have already done it might think, Well, this can be done.
Why are we doing it recursively in the purpose of doing it recursively is because I want this to be
kind of a slight Segway into a sub topic of occurrence relations.
And I think it will help us as a little introduction for a new topic, but I want to introduce in that.
So with that, let's go ahead and get started.
So the binary search algorithm, basically, it's a very efficient method of searching for an element
in a solid list of items stored in a subscript double container.
So what do I mean by that?
Well, basically it just needs to be a container that is index able.
So you need to be able to access an element at a given position that you might want.
So something like a vector or an array, etc..
And notice, they also said sorted.
So that is a prerequisite of the binary search algorithm.
The container must have the items sorted already.
So the idea is basically that we just decrease the size of our search space by half each iteration of
us looking for the value interested in.
This is something we call a decrease and conquer algorithm since we're decreasing the size of the problem
space.
So let's get into what that looks like.
So let's visualize it.
I'm just going to go over a very basic kind of vague introduction to this for a visualization.
And then afterwards, I will explain things in more detail as I do another example.
So here I'm just going to say we have an array and on the left at the very beginning, I have this little
arrow here called low in the middle.
I have this little green arrow called me.
And on the right, I have this little blue arrow called high, so low and high start out at either end
of the array from the very beginning, and the mid is always supposed to be in between those to the
midpoint in between those two.
And so what we're going to do is search for twenty nine.
And so basically.
If whatever Mitt is pointing to here is bigger than 29, we're going to say, OK, well, since this
container is sorted, if what I'm looking for is an.
Less so this thing here is bigger than I know that I only want to look over here, I don't care about
any of this over here anymore.
And also vice versa.
So the thing here is smaller than twenty nine.
That means that I don't care about this right here or any of this over here anymore.
So I want to look only at this.
And we're going to do that by moving these little low and highs around and adjusting the mid to being
between them.
So let's start for searching for twenty nine 14 is obviously not twenty nine.
So what we're going to do is move the low over here because we don't care about any of this anymore
and we only care about this sound.
So we're going to put the low in the high here and put this in between.
Now we look at forty one.
Well, forty one is bigger than what we're looking for.
We're looking for a twenty nine.
So we're just taking a look to the left.
We only have this to go off of because we already aren't looking at this anymore.
So now we're just looking here at twenty nine, which is actually what we're looking for.
And you notice that the low in the mid and the high are all at the same element.
So since the mid is pointing at twenty nine, that means we found it and we are done.
So pretty simple.
Let's break it down more so we can understand how this is actually happening, though.
So here I put the indices so lowest starting out at zero and high and starting out with the last index,
which is six.
So the way that we calculate our midpoint is actually by rounding down doing the floor of the low plus
the high divided by two.
So let's do that.
What is low, though, is zero.
High is six six plus zero is six six.
Divided by two is three evenly, so there's no need for rounding it down.
So that's where Ahmed is.
So the next thing to do is see whether we need to check to the left or the right.
So in this example, I'm looking for 30.
Thirty is greater than 14, so that means that the array made is smaller than 30, so that means we
don't care about the index three anymore or anything to the left of Index three since this associate.
So we are going to look to the right the way that we reduce our problem size, our problem space.
And for this example, is to move the low to one right from the middle.
And the way that we do that is pretty simple.
We just say low equals mid plus one.
Mitt is pointing at three.
So three plus one is four, and that's when we're going to move low.
So now we have a low pointing at four.
So we don't care about this or anything to the left since our container sorted and we know that 30 is
greater than 14, we're only considered in Worcester just to the right of it into the end of the container.
So now that we've done that, we have to reinstate Ahmed.
So we are going to say that made it a little farsighted available to round it down.
So we're going to do for as low plus high as six.
That's 10 10.
Divided by two is five evenly, so we can just move it there to five.
So we're looking for 30, 30 is less than forty one, so that means Pyramid is bigger than 30.
So in this case, we're going to do pretty much the exact opposite of what we did with Low.
So when we were moving low, we moved it to one to the right of mid four moving high.
We're going to move it one to the left of it.
So now we're reducing our problem, the space to just this one element.
So what we're going to do is move high from over here.
So high is six, but made minus one is four.
So we're going to move higher over here to four.
All right, so long hair in the same element.
Now we need to recalculate our men once again.
So if we do four plus four divided by two or that's just four, so men and low and high are all going
to be on the same element here.
Because we've effectively reduced our problem space again by half.
So now they're all pointing to the same element, let's look at men is mid 30, no, it's 29.
So ideally, you would just stop here if you're just looking at this basically like, OK, well, we're
done.
It's not in the array, but the algorithm actually keeps going just a bit more.
And you may be thinking, well, that's not good.
It's just going to be doing checks that it shouldn't be doing.
But let's see how it actually stops itself.
So we're going to just keep going and we're going to say, well, if arraignment is smaller than 30,
then let's look to the right.
So it is 30 is greater than 29.
So we do that same thing where we move low one to the right of mid, so low equals mid plus one.
So that means that low is going to move to index five.
So we move to index five.
And what actually happens now is that in our algorithm, we have a little stopping condition where if
lo ever crosses to the right of high, we stop immediately.
So if low is greater than high, we will stop and then we will return a negative one to show that the
number was not found.
So what does this look like in code?
Let's take a look at it.
So here is our stopping condition.
I said we're going to do a recursive algorithm, so we're stopping condition is going to be our base
case.
And it's going to be at the top here, just like base cases normally are.
So we're saying if low is greater than high, then just return a negative one.
So that's when the low and high cross.
The next thing is we have this little local variable that gets clobbered each time, but it updates
before this code down here, which gives us the middle.
So we see the main is the current level plus high divided by two.
So that's getting calculated.
Then what we do down here is we're looking at the condition in which the middle number is greater than
our number.
So if the middle number is greater than our number, that means that our number is less and therefore
we want to look to the left right.
So what we're doing is we're recursively calling the algorithm again.
Of course, passing our array, then we're passing the thing we're looking for.
We don't want to move the low because the thing that we're curious about is to the left.
And so what we're going to do is basically update Hi vaginosis, this last parameter over here to one
less than mid.
So that's us effectively reducing the problem space and looking on the left.
Different condition is this elusive right here, so I'll say, if you know, the middle number is less
than our number, so our number is greater than what Mitt is pointing at.
In that case, we're going to want to move the low.
So you see the low parameter is the second to last parameter here.
So what we're effectively doing is recalling the function where Lo is going to be one more than mid.
So we'll be looking to the right instead.
Otherwise, that means that we found it.
So it's not greater than or less than that means that it's equal to since we found it, we can just
go ahead and return the number.
So now let's move into how we would analyze the time complexity.
So if we look back at this code, let's think of how we could set up a recurring solution for this.
Well, what's happening here?
The base case happens when the problem size is one, so in low is greater than high.
That basically means that the problem size has been reduced down to one because there's only one element
in the container at that point in time.
That means, you know that they would be on the they would all be on that same element.
And then lo gets moved one over.
So when there's one, they're all in the same element.
That means basically that we only have one element left that we're considering.
So the problem size, the problem, space size has been reduced to one.
So because of that, we will be using something like T of one we care about when the problem sizes is
one, that's when we're going to have our base case.
And you notice that there's also like a basic operation here.
If we're considering comparisons, then we have a comparison right here.
And we also have a comparison right here because we have this greater than and less than so we could
measure for the number of comparisons here.
And then we have our recursive call, and so this is one of two possible recursive calls, and this
is another one of those two possible recursive calls.
So how would we set this up?
Well, you notice that these are the calls that reduce the problem space by half.
We talked about that in the very first bit of the lecture, how this algorithm is a decrease in conquer
and it effectively decreases the problem space by half every iteration or every function.
Call the recursive call.
So since we're decreasing it by half instead of us doing and minus one, we don't really have that.
Our input is not in in the parameters right here.
What's happening is that the problem space is the whole array.
And when we have it each time, then we can effectively say that, ah, if we're representing the problem
space as in so that's our size of the input, then it's going to be divided by two.
So each time we recursively call what you're doing and divide it by two.
So let's set up that recurrence relation, so what is the base case?
Well, we said the base case basically occurs when the problem size is one.
So we're going to say T of one equals one.
And you may be wondering, OK, well, why are we using one like that basic operation?
We said it was number of comparisons.
And so in this example, I'm just going to consider that constant here, even though we don't have a
comparison.
Because if you remember when I talked about their current situation, I said that it would end up with
the same complexity because in the end, we're just really kind of abstracting away all these constants.
And so this will make my problem easier to solve, and it's totally fine to just put some type of constant
for the base case because honestly, you could imagine that that's getting at it anyways.
There is an operation there, even if it's not the same as our basic operation.
That was something that I described before.
There was no multiplication in the base case, so I just put zero.
But it would have turned out similarly if I do take the base case into account and just added that one
extra constant operation because it would have been abstracted away when we got our final complexity
and used to theta or bigger notation.
So I'm going to say tier one equals one for that.
The recursive portion, we said that was going to be in divided by two.
The recursive call is can be represented by two over two.
And then one you can put plus some constant.
And why are we going to do that?
Well, yeah, we have multiple comparisons, right?
So comparison, basic operation comparison, basic operation comparison appear.
But if what we just said was that these constants get abstracted away anyways, so what we can do most
of the time when we're doing recurrence, relations for the time complexity is we can just say plus
some constant and some people just represent that as see.
Or you can just put one.
So I'm just going to put one.
So you could just think of one as just like some constant amount of operations because you remember
a constant time is just kind of a hard coded thing.
So if we have five, you know, or 100, when it comes down to it, it's not really changing.
So we can always think of it as of one.
And so I'm just going to represent that by putting a one here.
So now we have our recurrence relation.
Doesn't look too complicated, except this is kind of new here, right, because before we were doing
something like in minus one, and I think we've only gone over examples so far, I think I had maybe
a worksheet that I have included.
If you haven't seen that yet, it was just in my S-1 as well here.
And so now we're going into something with this division.
So let's see how that actually plays out.
So let's solve it via substitution.
So we're starting out, we have a base case here, and then we have our actual formula.
This is supposed to have tfn over that.
I'm sorry, doesn't have to give in.
So just imagine there's two of an around this with parentheses.
So.
When we start off, just kind of how we were curious about it, minus one, we're actually going to
look into T minus two right off the bat.
So this is kind of our first little mini substitution thing we do.
So we're going to substitute in over two into the main formula.
So imagine, of course, this has the tea with the parentheses wrapped around this, I forgot to put
that sorry.
So what we would do is if we replace in by an hour or two, we actually get in over two over two plus
one.
And so in over a two and then another over two is the same thing as two and over four.
So now we've figured out what to in over two is.
So what we can do now is we can take what to give it over to us and we can substitute that into where
we last left off, which is right here because we only start at the beginning.
So we'll substitute one over two equals two in and we were four plus one.
So we put that right here and there's this extra plus one there, so we can simplify this two tier of
tier in over four plus two.
So now let's look at this to you and our four.
And so for that, so and over four, we can substitute in over for four in so and over four over two.
It's the same thing as saying T and over eight.
So that simplified.
And we just had we substituted this in the original formula, because that's what this substitution
phase does.
That's what we do.
We substitute this in the original formula.
Now we know of in over for.
So if we look where we last left off, which is right here, this next line up, we can substitute this
tea in over for with this since we know the tea of in our for equals this over here.
So let's do that.
So we take this whole thing in and replace this right here with that.
So that becomes tive in over eight plus one and then the plus two.
That we left off with, so it's actually not here, sorry, it's right here.
This was our simplified equation, so.
We have this trend in over eight plus one.
It's actually replacing this right here because that's where we last left off.
So that is why we have this trend over eight plus one and then the plus two.
So that simplifies the trend over eight plus three.
So do you see a pattern yet?
We've only gone through a few iterations, but there's not a whole lot going on here, so you might
already be able to see a pattern.
So I see a pattern and what I see is I see this increasing.
And I see this increasing out here.
So we we have our end right here, but we want to look at these changing numbers, changing constants
over here, and how can I compare these two?
Well, for any given iteration for AI that were on?
And remember, what I'm trying to do with the pattern is find that I term some thinking about that iteration
that I'm on.
So what I would be?
So here I is.
One so.
If we have is one and then we have so I'm looking at these simplified things over here, remember,
I think back.
When I was first introducing it, I had them in yellow so that you can imagine like the yellow, things
would be right here.
So these right here.
We have the simplifications, so we have this right here and then this right here and then this right
here.
So yeah, this one in the beginning, then the next simplification phase was this right here for our
main formula here and we're looking at all the trends, events, right?
So here the team in here at the event, and here's Steven.
So we're considering this.
And to you in this year.
So we're considering this simplified form over here and here it is here.
So we're considering this.
So look at those three, this one, this one and this one.
And what I notice is that when I is one, we have the same thing as I over here.
So is one and this is one over here.
When I asked to.
We have this over here, too.
And then when I asked three, we have this three over here, so I'm matches up with that number, so
that could pretty much be I.
This under here, though, we start out with two and we're successively dividing by two.
You can think that the division is like the opposite of multiplication.
And so when I think about this, like repeated multiplication instead of division, that would basically
be like a power, because if you keep, you know, if you do two times, two times two, that's basically
two to three to two of the third power.
So if you think about it that way of it being a power, then that pretty much matches up with I.
Right, because two to the one is to.
And then when I as to if we have two of the two, that's for four right here, and if we go down to
this last kind of TV and example.
Two to three is eight.
And so if I say to Tether and then one and then two and then three.
So I mean, one and then two and then three for these numbers here.
They actually match up with with these and we said this was I.
They also match up with the idea where I as I as one here than I used to, and then I have three.
So I'm thinking that this down here can actually be represented with like successive powers of two.
So two to the eye and we said this was eye over here.
So I'm going to say is that we can represent this as humans to you in over two to the eye.
So this is all like you can imagine, this is kind of in parentheses and over to to the eye, it's not
in our tuned in today because this number down here is basically going to be raised to the power of
the given iteration.
And in this, we said, was the same as I saw.
I'm just going to put it there.
So this is what I'm going to choose from my term.
And hopefully you were able to see a similar pattern or at least understood it after I related to all
of these iterations we were looking at.
So this one, this one and this one.
OK, so let's move on, so now our next step is is to use the term with the base case, right?
So we notice that we have our item here in our base case with Tier one equals one.
So if I say this is the same as one, so what we do is we're going to assume our base case, right,
if you remember that from the previous recurrence relation lecture.
If I have one in between here, I'm just going to consider when the problem size this one, then I can
basically set what's in between here equal to that.
So in order to do that, I equals one.
And so if I want to simplify this, what I could do because what I want to do now is get it in.
Terms of I like I basically want to solve for I because I eventually want to be able to put this in
terms of end.
So I want to replace I with and I have it in here.
So I'm basically trying to get by to be equal to something of RN so I can replace it.
Right?
So what I'm going to do is multiply both sides by two to the I to get rid of this denominator here because
this is like a fraction.
So since it's divided by two, that if I multiply it by two to the I, it'll isolate and it'll basically
make this, I just end.
But I have to do the same thing to both sides.
If I do that.
So if I multiply one by two, I one times, you know, something times one is just a cell, so I end
up with an equals to the eye.
And so this is interesting.
What do we do now if we want to basically get AI to equal something within so we can replace AI within?
How are we going to do that with this right here?
Some of you might already understand what to do.
With this right now, but I'm going to ask I'm not assuming that anyone has any particular math background
for this, except maybe some very basic algebra.
And so for that, I'm going to kind of introduce logarithms.
So what we can actually do at this point right now is we can actually use an interesting property that
has to do with exponents and logarithms.
So like I said, just in case some of you aren't familiar with logarithms, I'm going to go on a quick
tangent to bring everyone up to speed on what is in the logarithm and how are we going to use it right
now?
OK, so black films are basically the opposite of exponents.
So.
If you're saying three squared equals nine, that can basically be reversed by saying log base three
of nine equals two.
So when we have three squared equals, nine two is the power that three is being raised to, so it's
the exponent.
But in log base, three of nine equals two three is the base of the logarithm.
And what we're really asking is the three raise to what power is nine.
So it's pretty much the opposite of an exponent there.
So you notice that what we do is that we actually move the three and the three squared equals nine down
to the base.
So it's basically a number that's being raised to the power that turns into the base.
And then the nine is always said equals nine, that's the thing you're taking long makes three of.
And then what you're looking for is the power.
So it's asking what the power is.
So a lot of base three of nine is equal to two.
So since we have this relationship, we can use this property to actually go back to what we simplified
to before, which was an equals two to the eye.
And we can say that it's the same thing as saying I equals log base two of and you notice that we take
the two and we make that our base.
We take the eye.
And that's the thing that we're actually looking for, which is the power.
And then we take the PN, which is on the other side of the equals sign from the exponent.
And that is the thing that we're taking log base two of.
So we're doing the same.
Rearranging is what I mentioned above.
And it's nice because when it does, that relationship can get this in terms of I.
And once we have this in terms of why we have, I equals one vs two, then now we can go back and we
can substitute EI by replacing an N in there, putting an end for IE in our current format, which is
what we wanted all along.
So let's list the things that we know so far.
So DeHaven equals this term, we have that, then we just found out that we can do I equals log base
to in because we rearrange that and equals to die and we have our base case T of one equals one.
And then we also know that we were setting in order to equal to one.
For that base case.
So with those in mind, we can basically say this right here, Tiven equals T to the one because we're
coming from our eighth time right here and we we can replace this with one because we have this right
here and then we can replace.
We basically said I.
Equals log base two to the end, so you notice that we were replacing this with one right here, so
that's what this is.
It's T of one instead of T over two I.
And then plus I always said, Oh, I think we're a long ways to an end so we can basically say this
right here.
And we already know tier one is one, so we can replace this with one so we can simplify to this one
plus long ways to event.
And we also know that we can abstract away the constant one.
And what we can also do is abstract, away this base to for our answer.
So now what I'm going to do, just because I'm just going to say it's big because I'm going to do an
upper bound.
I'm just going to say that and we can say that the answer is big of log in after we abstracted those
away.
So hopefully that broke it down for you enough.
You know, you could also do a tight balance for this and say data, but I just wanted to show that
we can use tobacco and of course, in industry, you know, a lot of times you're going to be looking
at upper bounds.
And so they use PAYGO.
So I said bingo.
So this is a little bit different.
We have this excessive division, might you?
But you noticed that it wasn't that much more difficult.
But this is going to be a good segue into our next topic, which is going to be looking at.
It's nice that we have this success of division by two, but it also is kind of problematic way to solve
the way we've been doing if we didn't have.
That that successive division.
So, you know, if it were slightly different, if it if it wasn't like a power of two.
So we're going to look into that soon as well.
So a few things that I want to know and recap on.
So just remember, a binary search requires the container you're using to be pretty sorted.
It also requires that you have an index of all containers, so you can't use something like a linked
list where you cannot index.
This particular element in that data structure cannot be a binary search on a linked list the way that
it is.
So we also recovered recursive implementation, but I wanted to mention that you can also do an iterative
implementation.
So I think I mentioned that before that some people might have already done this and they've done iterative
implementations so that it's totally possible.
And you could also solve the time complexity of that as well.
It would actually be the same time complexity, of course, the same algorithm.
The space might be different, but I'm not getting to that right now.
So that's pretty much it for binary search.
And with that, I will see you in the next lecture.