Hi everyone.
This question is about a very important concept called the binary search.
Now this is a very helpful method to search in data which is sorted now.
It can be numbers which are sorted either ascending or descending, or it can be characters or strings
which are sorted alphabetically, etc..
Now whenever you are doing any question where data which is given to you is sorted, think whether you
can solve it using binary search.
Now let's go ahead and read the question and let's try to understand how binary search works.
Given an array of integers, which is sorted in ascending order and a target integer, write a function
to search for whether the target integer is there in the given array.
If it is there, then return its index, otherwise return minus one.
You must write an algorithm with O of log n runtime complexity.
Now this is the catch over here right?
So let's say this is the array which is given to you over here.
And let's say the target value which you're searching for is 11.
Now you could do a simple search where you try to just go through the array.
Right.
You're iterating through the array.
You check whether this value is 11.
No it's not.
So you proceed.
You check whether this value over here is 11.
It's not equal to 11.
So you proceed, etc..
Right.
But in that case the time complexity is going to be o of n, where n is the number of elements in the
array.
But over here it's mentioned that the solution has to have a time complexity of O of log n.
So this is where the binary search comes into picture.
And remember o of log n is much, much better than O of n or linear time complexity.
And we have already discussed that in previous videos where we discussed the time complexity, right?
For example, if n is equal to, let's say four, right?
So if n is equal to four, o of n will be four o of log, n will be equal to only two.
Because we know log of four is equal to two.
Right.
Because what is log n.
It's actually the power of two.
You have to raise it to so that you get this four over here.
Now two to the power two is equal to four.
So that's why log four is equal to two.
Now similarly if n is equal to let's say two to the power 100 right.
So this value over is value over here is going to be a very big value.
But when we do O of log two to the power 100 this is only going to be equal to 100.
Now you can see that there is a huge difference between these two right.
So that's why the binary search is a very useful algorithm.
So let's proceed and go ahead and develop some intuition about how the binary search works.
Now remember this works only when the data which is given to you is sorted.
Now let's take an example in daily life.
So over here you have your teacher, and the teacher has answer sheets in her hand.
So there was a recent exam and she has evaluated it and she has sorted the answer sheets as per the
roll number of the class.
All right.
Now let's say she has sorted the answer sheets over here in ascending order.
So these are the roll numbers 1 to 10.
Now let's say you want to find the answer sheet of roll number seven.
Let's say your roll number is seven.
And you want to find this answer sheet from this pile of answer sheets.
Right now one way you could do is you could go through one by one.
But another way, typically how you would have done it in class is, let's say you opened it up to this
part over here and you can see that it's six, right.
So you are opening it to the middle.
You see it's over here.
The roll number is six.
So you can be sure that the answer sheet with roll number seven is not going to be in any of these parts.
Right.
So you can just directly eliminate the whole of this part without even looking at each of these individually.
So that's how the binary search works right now.
Again remember the opposite of it.
Or the alternative is the linear search.
Now in the case of linear search, as we discussed, you would be just checking one by one till you
reach the roll.
Number seven.
Now this over here, this operation over here, which is a linear search, is an O of n time complexity
operation.
So and then we have seen that in this question we need a time complexity of o of log n.
All right.
Now one more interesting thing which we can observe over here is inbuilt functions in JavaScript such
as index of etc. operate in this manner.
They are just going to search one by one, and the time complexity of these type of operations, like
index off is going to be O of n.
Now for example, if this was the array and let's say this array was numb's.
So then you could have just done numb's dot index off.
And let's say you are searching for seven.
You could say Numb's dot index of seven.
Right.
So that would give you back this index 012345 and six.
So this is index six.
So it will give you back the index which is six.
Built in functions in JavaScript such as index off actually under the hood are doing a linear search
which is an O of n operation.
All right.
Now let's go ahead and think about a little bit about what are the interesting things that we can note
about the binary search algorithm.
This is going to be a divide and conquer algorithm, where we are going to divide the array which is
given to us into two parts at every step.
And we are going to eliminate half of it at every step.
So that's how the binary search.
Got them works.
And remember this will work.
The caveat is you can apply the binary search only if the data which is given to you is sorted.
So this is very important.
If it's integers, it can be ascending or descending, or if the data is strings it can be alphabetical,
etc..
In the next video let's try to understand the method and the.
And then let's go ahead and do the complexity analysis of the binary search algorithm.