Hey, guys, what's up?
So today we are going to learn binary search, OK, so the problem with the linear search is that it
doesn't take into consideration whether the given is sorted or sorted.
OK, so we will use binary search for software that is.
So there's a condition, condition used by news such as that area must be sorted.
OK, so binary search can only be applied if the given that is sorted.
If that is unsorted.
If I have unsorted.
Eddie.
Then binary search cannot be applied, we have to apply linear search only.
OK, so linear search is the only option if we have unsorted every.
But if we have sorted that, we will always use binary search.
OK, so let's see, so we will take an example and we will try to understand how binary search works.
So suppose my ETAs, so it must be sorted, so let's see.
So these are indexes zero, one, two, three, four, five, six and seven, and let's say the values
are two, four, five, eight, 20, 23, 40 and 49.
These are the values.
For example, I want to search for let's say I want to search for food, so how my new search works,
it takes two pointers.
So this is a start and this is end.
OK, so then it will calculate.
So Americans start plus.
And by doing that is zero plus seven by two.
So three point five, which is three.
So.
My mate is here now, there are three possibilities, so first possibility number one, if the value
president had made.
Is it close to the given we're lucky if this is the case.
I will return.
OK, so I found the key and the key is present at the next second possibility if the value added is
greater than the key.
So in this case, for example, it is greater than four, then I can say that my answer, that key will
lie only in this part.
OK, we cannot lie here, so I will discard this part.
So what I will do and it was made minus one, so my end will come here.
OK, and how can I discard this part?
Because I know this is amid all these values.
On the left hand side are smaller than mud and all the values on the right hand side are greater than
mud.
So these values are less than made and these values are then made because my ad is certain.
So if the value present at Miller is greater, then that means we can only only only lie in the left
part so I can discard the right part.
OK.
And similarly, if.
Murder is a less denki then, so this is my murder.
This is right and this is left.
So right values are greater than murder.
So if my murder if the that murder is less stinky, then my answer will only lie in the right part.
In that case, I will.
Ignore the left part and what I will do.
Start equals method plus one, so many will come here so they start will come here.
And my problem is not only this, I have to search only on this part.
OK, so let's take an example and we will see what happens.
So.
So zero, one, two, three, four, five and six, and the values are two, five, eight.
13, 15, 20 and 25, and I want to search for value, let's say Geike was search for five, OK, so
first of all, this is start.
This is my start.
And this is my and now I will calculate made so many calls start, which is zero plus and which is six
by two.
So Mayday's three now this is my murder.
So compare the value is 13 equals five.
No logic 13.
Guerdon five.
Yes, the condition is true.
My answer will lie in the left part.
So I will discard this.
So and it was made minus one, so that is three, minus one at two.
So this is my end.
This is my end.
Now I will again calculate so murder equals start, which is zero, and which is two by two, so it
is coming out to be one.
So this is murder.
This is murder.
Now, again, I will compare is five close to five.
Yes.
Then what I will do, I will return mid, return mid.
So I will return the next one.
OK.
So this is how by research book.
Now, let's take one more example.
So suppose the adays.
Zero, one, two, three, four, five and six, and let's say the values are one, four, five, 10,
12, 18 and 25 and I want to search for, let's say, 25, OK?
I want to search for value 25.
So this is my start.
This is my end.
First of all, calculate the milk so many medicos start plus and buy two, so many clothes, three.
OK, so this is my mid.
Now, compare is 10 equals 25.
No, the second condition is stronger than 25, no, and less than 25.
I guess the value is less than key.
So I will search on the right hand side that is and equals three start equals murder plus one.
So much is three plus one.
So this is four.
So now this is my updated start and I will discard this whole part.
Now, what I will do, I will calculate again, so Americans, you start there's four and there's six
by two, so is coming out to be five.
So this is my mid.
Now, compare is 18, close to 25, now is 18 and then 25 now is 18, less than 25.
Yes.
So what I will do is start equals murder plus one.
So it is five plus one.
So start equals six.
So discard the left hand side.
Now, this is my start.
OK, now I will calculate Made against America's Start plus, and by doing so, it is coming out to
be six.
Now compare.
So is AOF six.
That is 25.
So is 25.
Equals 25.
Yes, the condition is true.
I will return MD and Maydays six, so I will return six and add the next six.
The value 25 is present.
OK, so this is how by new search work.
And now let us take one more example where the key will not be found.
OK, so this is my area.
Zero, one, two, three, four, five, and let's say six and seven, and the values are two, three,
four, eight, 12, 15, 20, 27, and the values that I want to search for is let's say five of five
is not present here.
I want to search for five.
So this is my start.
This is my and now let us convert the value of the murders of miracles, start bless and buy two.
So it is coming out to be three point five, which is three.
Integer upon integer will be in integer.
So this is my ID now compare it equals five.
No eight then five.
Yes.
So what I will do and it was made minus when that is what is the value of three.
So three minus one so and equals two.
So this is the new value of end.
And what I will do, I will discard the right hand side.
Now, again, calculate what is the value of milk, which is start plus and buy to sell to buy two is
one.
So this is my.
This is made.
Now compare the value of milk.
So is three equals five.
No.
So is triggered then five.
No.
So it's three.
Less than five.
Yes.
So what I will do is start equals murd plus one.
So what is the value of made.
So one plus one.
The value of start is to so start will reach here.
Now again calculate the value of milk which is start plus and by doing so four by two is two.
So this is my mid.
This is mid.
Now, what I will do, I will compare the values, so is four equals five no is for them, five no.
So is for less than five.
Yes.
So what I will do is start equals murder plus one.
So what is the value of Modesto's or two.
Plus one.
So start is three, so my start will come here.
So this is my start.
Now, what happened is start is three and is two.
This is a start and this is end, OK?
So what happened here is start becomes greater than end.
So if this is the condition, that means I can say I will stop and I will report that the key is not
present, key not found.
OK, so if my start becomes an end, I will stop and I will report my answer that the given key is not
present in the Eddie.
OK, so this is how binary search works.
Now, let us try to find how many number of steps by new search will take.
OK, so what I am doing, I am calculating the value of the method, which is a start plus and two,
and then I'm comparing with key, I'm comparing these two values.
And each time I'm comparing these values, what I'm doing, I am reducing my number of elements on which
I have to search.
OK, so if is Denki.
And it was made of minus one.
So if there were any elements, so I suppose there are any elements.
This is made and if this is good denki what I did, I will put my pointer here.
This is start and this is end.
So this is my new search space.
We will only be present here, otherwise we will not be there.
So initially I was searching on any elements then I am searching on envie two elements.
OK, and we will repeat the same process here also, I will admit I will come key and similarly, if
it is less than what I will do, start equals murder plus one.
So start will come here and I will discard this part.
So again, these are and by two elements only.
So what I am doing, I am decreasing my search space by two.
So next time I will search on and buy four elements.
Then end by eight elements and so on.
OK, so each time I am reducing my search of space, the search space means the number of elements on
which you have to search.
You have to perform a search operation.
So what is happening here?
Initially, I have to search.
And elements, then I will calculate and then compare, then I have to search in and buy two elements,
then I have to search for and buy four elements.
I will search in and buy four elements for the gunky and it will keep going on.
Let's see the number of steps in binary search is key.
OK, let's say a binary search takes steps in binary search take steps so finally end upon to the power
key.
OK, so when this Minnesota will stop, when there is only one element in the area so and to a close
one, that is this Minnesota will stop only when there is only one element in the area because I cannot
divide one element into two 1/2.
OK, so and it goes to the patchwork taking log on both the sides.
So log and it goes back log to and K equals log and with the base to.
And I told you that constant doesn't matter.
So Keiko's log of N constant doesn't matter.
So give us the number of steps.
And this is a log and it's a binary search, binary search takes log off and steps.
So what is the time complexity of binary search?
It is big off log and and linear search time.
Complexity of linear search was off.
And so this is for sorted Eddie.
OK, so if the given that is sorted, then binary search is much, much more efficient than linear search.
OK, so this is it for this video and next video, I will write the code for Binary Search.
OK, so if you have any doubt, feel free to ask.
Thank you.