OK.
Welcome back to another lecture, we're going to continue on with the topic of searching and searching
algorithms in today's lecture is going to talk specifically about a new search algorithm called the
binary search.
So let's think about what we've done so far in searching, which is only leading our search.
Is there a faster search?
Do you think there's a faster search?
Are linear or sequential?
Search had to go through every single element, which makes sense, right?
Because if the elements are out of order, then the thing we're looking for, it could be anywhere inside
of that vector array.
So we need to check every single position, right?
Because it could be any one of those positions.
But what if, hypothetically, all of the elements were sorted and sorted in ascending order?
So think about that and think a little more specifically, if I'm looking, let's say, for the number
five in an array of vector that is sorted.
Let's say I checked some position near the middle of that array or vector, and I noticed that there
is an element six there.
So the item is an integer, which is the integer six at that position.
So some middle of the array, whatever to that position, might be somewhere near the middle.
I find an item that is six.
If I find this item at six and I'm looking for five, does it make sense to look further to the right?
Of where that six is.
So think about this, does it make sense for us to look further to the right if the array is sorted
and we're looking for the number five?
So the answer is, no, we do not need to look further to the right because everything to the right
of six is not only bigger than five, it's bigger than six and six is bigger than five.
So none of those numbers are of interest to us.
In fact, we can pretty much pretend that the list is only everything to the left of the position that's
holding the number six.
And this is the main mechanism of binary search.
It basically cuts out the parts of the array of vector that we don't need, and it makes the area that
we have to search much smaller each time we do this.
In turn, this speeds up the overall searching process by a lot.
So let's see how it works, exactly, we're going to look in a more detailed example here, I have eight
items in an array or vector.
What I'm going to do is I'm going to start at vector dot size minus one divided by two.
So what is vector dot size minus one?
It's seven when I divide seven by two.
It is three, so we're doing integer division right here.
So what we're really doing, which you'll see in the rest of the algorithm is we are adding the first
position, which is zero plus the last position, which is seven, which gives us seven zero plus seven
kind of in parentheses here.
Divided by two.
Except I didn't put the zero there because it's zero.
So we're starting out right here at three, so it's kind of near the middle.
The actual middle since there's eight items, is this line right here, but we can't just be on the
line.
We got to be in an actual position.
So we kind of like our rounding down to this three right here.
So let's see, the number we're looking for is 22 is 22 greater than nine or 22 less than nine.
Well, it's greater than nine, so we want to look only to the right of nine.
We do not want to look to the left of nine.
Right.
So what we're going to do is pretend this part of the array is now invisible.
We're not going to change the position numbers.
We're just going to pretend that is completely invisible.
We have no interest in it.
We only have an interest in what was to the right of nine right and the right of nine starts right here.
So we now need to find a new middle for this sub array.
Right?
So what we're going to do is the same thing.
We're going to add the first position index, right, the first index, plus the last index.
Add those together, so seven plus four is 11, and then we divide 11 by two and we're going to get
five because we're doing integer division, so that will give us our new middle to consider.
And each time that we're doing this, when you see a green square, we're also checking, you know,
we're of course seen as a greater or is it less than, you know, the number we're looking for, but
we're also curious about whether it's equal as well.
So if any point in time, the green square here was equal to twenty two, we would know that we found
our answer.
So we take a look at this 16, so is 20 to greater than 16 or 20 to less than 16, well, it's greater
than 16.
So once again, we're going to ignore everything that's not to the right of 16, so we're going to ignore
16 and 14.
So we pretty much make those invisible.
And now we're left with these two items.
Here we have six and seven.
Once again, we need to calculate a new middle.
We do six plus seven, right?
So the lowest plus the highest index.
So we have six plus seven is 13 and we divide 13 by two and that gives us six.
So now we are in position six and we'll look at that.
The number we're looking for is twenty two and just so happens that we found twenty to twenty two is
not greater than doing two or less than twenty two.
It is equal to our answer.
And so we have found it.
So we found her answer pretty fast.
I mean, compare that to us having to look at all the elements like in linear search.
So if we were doing linear search, we would have to just start over here and look at this element,
then look at this element, then look at this element, then look at this element and that one and that
one.
And then we would finally arrive here at our answer.
But that's a lot of comparisons.
If we go back, we noticed that we only did a few comparisons, so we started with nine nine wasn't
the answer.
Then we looked here at 16 and 16 wasn't the answer, and then we found her answer.
22.
You know, that's a lot less than going through all of these positions until we, you know, we looked
at each one of these things up until here.
So this is a much more efficient algorithm.
So I'm not going to go over the details of how fast each one of these algorithms is and why it's that
fast because we're going to do that later on in the algorithm section of the course.
We're going to look into this in great detail.
If you want a solid answer, though, just to be able to say, you know, linear search, is this this
fast and binary search?
Is this fast?
You can say that linear search runs in linear time and binary search runs in logarithmic time, except
I haven't really explain these concepts.
These are things that you would have to look into, but I don't think that's necessarily the best idea,
because later in the course, we're going to dive deep into analyzing these algorithms and understanding
what it means for something to run in linear time or logarithmic time.
The only thing that you can like think right now is that or know is in linear time is actually slower
than logarithmic time.
So therefore binary search is faster than linear search.
But we're going to get into that later.
So let's look at another example where we do not find the item that we're looking for.
So let's look for four.
So what we're going to do is the same thing we're going to do is zero plus seven is seven seven, divided
by two is three.
So we'll start off at the same position, right for the middle.
We're going to get rid of everything over here to the right because we're looking for four.
Four is less than nine.
So we don't care about nine or anything over here.
So what we're actually doing now is we're moving our high.
So remember, we were doing like a low, which is zero plus high, which is seven to zero plus seven.
And we got took that answer, which is seven divided by two equals three to get the middle.
We're going to do the same thing here.
So now only get rid of that.
We're basically going to say that our new high is two because it's one less than where we were right
here, right?
So three minus one is to our highest two and our low is zero zero plus two.
Is to do to limit you is one, so now we have a new middle here on one.
So is for less than three.
No, it's not for greater than three.
Yes, it is.
So we're not interested.
We're not interested in any of this right here.
We're only interested in here.
So now we have one element left so pretty interesting.
So we're not going to find our answer here.
But what we're going to do to get the middle is what we've been doing so far.
So we're going to move the low and high index.
So we're going to move the we're going to check for four fours less than six.
So what we will do is we're actually going to say that the high is going to be one less than what it
currently is right here.
The high and low are the same ones, right?
Currently, low equals two and high equals two.
Since we're only on one element, there's only one element left.
If we do, high equals mid minus one.
So two minus one is one suddenly high is less than low, right, our high index is less than our low
index.
So low is two and high is one that doesn't really make sense, right?
The high shouldn't be less than the low.
So this tells us to stop looking.
Unfortunately, we haven't found our item and now we can give up with our search.
So let's go ahead and go write some code.
So head to your favorite editor and we're going to go ahead and write this binary search.
And to clear that up.
And what I'm going to do is go into the first program and the searching folder here.
So I am going to actually open up this binary search to CP, where I have an empty function skeleton
and an empty main function skeleton.
I'm going to make a binary search function that's a yes or no answer.
So it's a boolean that it returns and it takes in the vector, which has the items and also takes in
the number that we're searching for.
So these are both the parameters.
And what is going to do is to run the binary search in this function and return whether the item was
found or not.
So let's go ahead and make some stuff in.
Of course, I want to make a vector of integers and I'm I call this my vector and I actually want to
show you a new thing that you can do.
You can actually initialize a vector like this with hardcoded values, not from user input just in your
program.
So you can put a bracket like this and you can just be like one three eight two four four five six seven
and let's just do that.
So I just made a vector here that contains these items.
By just using the curly braces and, you know, an open, enclosed, open and closed curly brace and
then comma separated values in between, so you're able to make an initialize a vector like this as
well.
Except one thing is that you do need to be using a version of C++ like the compiler that I believe is
above C++ 98, I think.
But I think that you probably should be using C++ 11 and above, no matter what you're doing, just
because that has all the nice features.
So just want to point that out, though, if you're using an older version of C++ when you compile this
program, it might say, Hey, you can't do this right here with this style.
So just be aware of that.
So another thing that we're going to do is make an integer called number because we want the user to
also be able to enter a number, right?
Let's go ahead and get that number right away.
So I'm just going to see out.
I'm going to say enter a number to be searched in the vector because we just already have a vector,
right?
And then we'll say, see it, see in into the number.
And so what we're going to do now is we're actually just going to send the vector into our binary search,
the vector and the number to see if we can find it so.
What I want to do is I'm going to put an F because my binary search function returns a Boolean so I
can use an F right here and I'll just have the f be dependent on the return from the function so I can
just put a function, call right and say binary search, and I'm going to just pass my act and I'm going
to pass the number.
And so if this function call returns true, then the F will evaluate to true and the code inside the
F will be executed so we can just print out.
If that's the case, that means we found it right.
So we'll say, say we let's just say we found the number number in the vector.
So how about that?
Inline and then we'll say else, and then we'll just say we did not find meaning.
No, no.
And the victor, of course.
Cool, so we can just leave it like that.
And so let's go ahead and figure out our binary search now.
All right.
Because we got everything else set up, we're just going to call binary search here is going to tell
us whether it actually found it or not.
And then we can print out the proper message.
So what are we going to do for binary search?
Well, one thing, one thing that we're going to need is some local variables, right?
We need to represent that low index and that high index, and we're going to keep changing the low and
high index.
And that's going to tell us whatever's in between low and high is the region of the vector that we care
about.
Remember, the rest kind of turns invisible because we realize we don't need to look in those sections.
Low and high are going to be these little sliding kind of windows that show us what parts of the vector
we're going to want to look into.
OK.
So I'm going to say and low equals zero to start out with and then I'll say and high equals v right
v is the variable we have right here.
That's local to our function.
And it's also passed by reference, if you notice.
So I'm going to do in high equals v that size minus one, because that'll give us the very last next
to start out with, right?
Think back to the example we had zero in the beginning and then we had seven at the end because we had
eight items, right?
And we were using zero plus seven equals seven, divided by two.
That gave us three, right, which was supposed to be our middle, our starting out middle right.
That is the first middle that we have.
So this will give us a proper, low and high.
I'm going to start off immediately with the wow loop.
And how long do we loop?
What was our stopping condition if we didn't find something?
Do you remember what that was?
It was when the low crossed the high or vice versa, when the high crossed the low.
So low should always be less than or equal to high.
Remember when we had low and high, we're equal to two and we had the number six, but we were looking
for four.
We didn't find it, and what we did was we let high become one less than the mid.
So instead of two, it was one and then suddenly now low was still two.
Yet high was one and so high cross to the other side of low.
That's problematic.
That means that we need to stop.
So that's going to be our stopping condition for the loop.
And if that happens in a loop starts, we know that our item wasn't found because we went through everything
until the point where low crossed high and there was nothing left for us to look at.
So that's why many analysts say if low while low is less than or equal to high, we can loop.
And then what I would do inside is immediately calculate me because we need to.
That's the first thing we need to do is figure out our midpoint.
I'm just going to call this middle and I'll say middle equals, and I'm going to say in parentheses,
low plus high.
So remember this formula?
This was like the zero plus seven that we started out with, right?
So low plus high divided by two.
Now all we need to do is do our f checks, right?
So we're going to say.
Um, if, uh, the no, actually, it's just numb right now, so if none is greater than the index middle,
so this is the actual thing that we're on right now, right?
I can go back here.
Let's go ahead and go back here.
So this is like the middle, for example, right?
This is the first medal.
So we index middle would be nine in this case, right?
And we're looking for four in this example.
So we know that it would be left of nine.
So I just want to point that out back to the example.
So if none is greater than in, so that means that to the right, right, if it's greater, then we
have medal.
We're going to want to only consider stuff to the right.
So what are we going to do?
We're actually going to say Whoa, equals middle class one.
And why are we going to do that?
Well, let's think about it.
This is the mid right minus three.
The thing at mid position is nine.
If we're looking, let's say not for four, let's say what we're looking for is greater than nine.
Let's say it's twenty two.
Again, if we're looking for twenty two, that's greater than nine.
We know it's only going to be in this zone over here and we only want to care about this zone.
Remember that what we did was we cut this, we cut all of this off.
So what was our low it was for?
Four is one more than three.
So what we're doing is we're saying low equals middle plus one in the example, this is three plus one,
which gives us four, right?
So that's what we're doing if we want to look to the right where none is greater than what we're currently
looking at.
So that's what we're going to do.
Low equals middle plus one and else f.
All right.
This is if none is less than the middle I had less than remittal.
We're going to do the opposite.
We're going to say high equals middle minus one.
Why are we doing that?
This is the perfect example.
Four is less than nine, right?
We're looking for four.
It's not over here and it's not right here.
So it's only over here.
So what do we do to be able to have a new low and high?
Well, we need to make high go from three to two.
So what we're going to say is middle is three, right?
Let's do one less than middle and that's our new high.
Right?
So we'll go ahead and we'll do that, we'll say high equals middle minus one.
And if you're thinking, well, what about low, just think about this is the starting example, right?
Low is zero.
High is seven.
Middle is three.
We know we want to look to the left now.
We're not going to move low from being zero.
We're not going to change low.
Low is zero, right?
We only want to change high.
So instead of seven, we're going to say now high is three minus one, which is two.
So high gets this value.
Low stay is zero, which is good because that's all we care about, right?
We want this.
So we we went from this to this now high and this example is two.
So that is represented by this code right here.
If NUM is less than what we're looking at, we're going to say hi to minus one.
So what's the last condition in here that else?
If something isn't greater then or less than the only other logical option is that it's equal to right.
If it's equal to, we found it.
So all we're going to do is just return true because we've found it.
We know that we know that it's in there.
Our function is a Boolean function, right?
So this Boolean function is going to need to return true if we've seen our value.
And what does that mean?
It means that NUM is not greater than V middle or less than V middle number is equal to the middle.
It's the thing that we're currently looking at is the same number.
In that case, we return true.
So we have all three of our cases represented here, and we have the code that updates the middle each
time, right?
So we have a new middle.
Inside the IFS, we're actually updating our low and high correspondingly, so all that's left is that
if we stop the loop right, if we make it all the way through the array.
And what I mean by that is we keep having that happening and having cutting our array in half or a vector
in half to the point where there's nothing left it in the loop will stop because low will be less so
high will be less than low.
And, you know, or low could be greater than high.
Those high and lows will cross.
And in that case, after the while loop, we're just going to say, well, we didn't find anything,
so let's return false.
All right.
So just a little recap.
We start out with low as zero always.
We start out with high as the last element.
Always.
We start our loop.
Our loop is based on the fact that low and high should never cross.
Low should always be less than high.
High shouldn't go less than low, low and go greater than high.
If that happens, the loop will break.
That means that we have keep chopping our list or our array or vector in half until we just didn't find
anything, there was nothing left.
So that's why there's a return false down there, this middle update to the middle each time to the
actual middle of whatever between low and high by integer, divided by two.
This if check is if we want to look to the right, if the number we're looking for is greater than what
we're currently looking at inside the vector.
We need to go to the right.
That means we need to move low, right?
We're not going to move high, but we're going to move low one right from the middle.
Otherwise, if it's the opposite case, if the number we're looking for is less than what we're currently
looking at in the vector, we need to change the high low stays the same.
Yet high needs to be one less than what we're currently looking at, right?
One less than the middle.
Otherwise, the logical only other option is that it wasn't greater than or less than it was the exact
same number, and we found it over time.
True.
So that's just a little recap.
We have everything else set up here.
So let's go ahead and save this and run it.
Compile pilot, of course, first.
So give us first binary search.
So I'll just call this that the researcher out.
All right, so middle was not declared in this scope.
Let's see what that problem is.
I think it's just because I put med or something like that, probably.
So at the.
Oops and middle.
Yeah, so what I'll do is, I'll just put it know right here and then I can change it in there.
Yeah, this so this is the problem right here, exactly what I was talking about, so let me run this
again, clear it and run it.
So it says in C++ 98, my work must be initialized by a constructor, not by an initialization list,
which is what this syntax is right here.
So what I'm going to do since I have an older version of C++ running by default here is I am going to
add a little compiler flag where I go hyphen hyphen study.
So a standard equals C++ 11 eight.
So I run that again and no problems.
I run this list.
Enter a number to be searched in the vector.
Well, we have our numbers right here above us thanks to the error, right?
So let's search for.
Let's search for forty four, so we say forty four says we found the number forty four and the vector.
Let's run again.
Let's search for like eighty eight.
We did not find the number eighty eight in the vector.
Let's run it again.
Let's search for three.
We found the number three.
Let's run it again.
With social one, we found the number one inch or some crazy number like this or something like that.
We did not find the number three thousand fifty four, so you can see that this works pretty well.
So that is actually all I have to say about binary search, it is really good, though it that is a
really fast algorithm.
I mentioned that it runs in logarithmic time.
You don't have to look too much into that.
We're going to talk about what logarithmic time, linear time and even other times are when we go over
runtime complexity, time, complexity and general, that's in the algorithm section of the course,
the data structures and our rhythm section.
I'm putting that off because it is slightly more complex topic and we actually will get into analyzing
these things mathematically in that portion of the course.
We'll do a brief introduction and then we will go over a in-depth analysis of algorithms as well.
OK.
So if it's possible to have a sorted array, if you're a sorted, you should use binary searches much
faster than linear search.
So just take that as a note, and I will see you in the next lecture.