Welcome back.
Let's now go ahead and code the solution, which we discussed in the previous video, to search in the
matrix for a target value.
So let's call this function search in matrix.
Now this function is going to take in the matrix and the target value.
And remember the matrix is just a two dimensional array or an array of arrays.
That is an array where each element is an array itself.
All right.
Now we are going to do one binary search to identify the row in which the target value can be there,
if at all it is there.
And then we will do one more binary search on that particular row to identify whether that target value
is there or not.
So this is how we are going to proceed.
Now, to start with, let's just identify the number of columns and rows in the matrix.
So we can say const columns is equal to matrix at zero dot length.
Right.
This is the length of one of the elements of the matrix.
And in the question as per the question, every array is going to have the same number of elements.
And let's also go ahead and find the rows.
So we can say const rows is equal to matrix dot length.
So the number of elements in the row will give us the number of rows.
All right.
So we find the columns and the rows in the matrix or the two dimensional array which is given to us.
Now let's go ahead and start the binary search to identify the row.
All right.
So let's say top is equal to zero and then bottom.
Is going to be the number of rows minus one because it's zero indexed, right?
So top is zero.
So bottom has to be number of rows minus one.
All right.
So we are again doing the binary search over here.
All right.
So we'll have a while loop.
So while top less than equal to bottom.
And then we'll keep looping.
So this is how we go about it.
Now let's also have a variable middle.
Let me initialize this over here.
All right.
So once inside the while loop we will calculate middle.
Middle is going to be math dot floor.
Top plus bottom divided by two.
All right.
So we are going to find the middle row.
Now what we will do is we will check the beginning and the that is the first and the last element in
this particular row.
So let's check.
So if target.
Is less than the first element in this row that is matrix at row middle.
And at index zero in that particular array, because we know that matrix at middle this over here will
give us an array.
Now in this array we are going to check the zeroth index element.
Now that's the lowest element in this array.
Right now if target is less than this element over here that is the zeroth element at the element at
index zero in the middle row of the matrix.
If target is less than this value, then we are going to change bottom because we only need to look
at from top till middle minus one.
So bottom is going to change to middle minus one.
So this is binary search right.
So you can see that this is nothing but binary search.
Now let's proceed.
Else if this is not the case that is if target is greater than the largest value in the row middle that
is matrix at middle.
And the index would be the number of columns minus one.
So we are doing minus one over here because the columns are zero indexed.
Right.
So the first over here is zero.
That's why even though there are column number of columns.
So we have identified the number of columns we have to do minus one over here to get to the last index
in this particular row.
Now if target is greater than this value over here then we can we only need to look at the rows which
are greater which which are which are below this particular row.
Right.
Because we have we, we have seen that the rows are sorted from left to right, and the last value of
a row will be less than the first value of the next row.
So we have seen that right.
So for example let's just visualize this over here.
Let's say the matrix is having the values one, two and three.
And in the next row it's four five and six.
And let's say in the next row it's seven eight and nine.
For example, we are let's say we are searching for element eight.
Now middle as per this would be this row.
Now over here the last element is six.
Now target which is eight is greater than this six.
Right.
So we only need to look at rows which are below it.
So that means we can change top.
So we can change top to middle plus one.
So you can see that this is nothing but binary search.
Now if this is also not the case else that is if target is within the range.
So target is not less than the lowest value and target is not greater than the largest value.
If that is the case, then we can just break out and we have identified the relevant row in which we
need to have our next binary search.
All right.
Now, once we are outside this while loop, let's just have a check whether top is greater than bottom
right.
So there are two ways that we can come out of this while loop.
One is through this break right where, which means that we have identified the relevant row.
And the second way to break out is, is if top is no longer less than equal to bottom.
So if top is no longer less than equal to bottom, when we come out of this while loop, that means
that the target value is not there in the given 2D matrix, 2D array, or matrix, and we can just return
false.
All right.
Now, if this is not the case, that means that we only need to check in the middle row, the row which
is in the variable middle right.
So because we have seen that we have we have broken out over here.
So that means that target is in between the lowest and the largest value of that particular row.
So let's again go ahead and do one more binary search on the row which is now stored in the variable
middle.
So let's go ahead and do that.
So for this let's have two variables let's say left.
So left is going to be equal to zero.
And then we'll have right.
So right is going to be the number of columns minus one.
So this is again just normal binary search.
Now let's also have one more variable.
Let's just initialize it to mid value.
All right, now we'll have a while loop.
Now this is going to loop as long as left less than equal to right.
Now inside this while loop over here we are going to calculate the mid value.
And mid value is going to be equal to math dot floor.
Left plus right divided by two.
So we have found the mid value.
Now we are going to check whether the target value is equal to the value in the middle row at this index
which is mid value.
So let's just check that.
So if target.
Is equal to matrix at row middle.
And at index mid value in this particular row.
Right.
So if this is equal to target then we can just return true because we have found the value.
Now if this is not so let's proceed.
So else if target.
Is less than whatever we have over here.
Matrix at the row middle at index mid value.
So if target is less than this then we only need to look towards the left part from the mid value right.
So we can say that right is going to be equal to mid value minus one.
And if that is not the case that is if target is greater than this value over here that is matrix at
row middle and column mid value or index mid value in that particular array.
If target is greater than that, then we only need to look towards the right of mid value, which means
that we can set left is equal to mid value plus one.
All right.
So this is just binary search.
So we have done this before.
Now once we are out of this and if we have not returned true then it means that left became greater
than right.
And we were not able to find the target value in that particular row.
And then we can just return false.
So that's it.
So this is the function.
So let's go ahead and test our function.
So let's call this function search matrix.
And let's have an array also.
All right.
So let's just have an array.
Let me just write this over here.
So for example let's have 123 4 in 1 row.
And let's have.
Five, six, seven and eight in the next row.
And let's have nine, ten, 11 and 12 in the third row.
And let's have one more row.
So let's have, let's say 20, 30, 40 and 50 in the last row.
So this is going to be our matrix.
So you can see the matrix will have four elements.
And each element is going to be an array with four values.
So let's go ahead and define our matrix array.
So matrix is equal to and the first element is 1234.
The second element is 5678.
The third element is 910 1112.
And the last element is going to be 2030, 40 and 50.
All right.
So we are going to search for this in in this matrix for a particular value.
So our function is search in matrix.
So let's call our function and let's pass in the matrix.
And let's say we are searching for the value 12.
Now our expectation is that we should get true because you can see it's there in our matrix.
So let's go ahead and search for it.
And you can see we are getting true, which is correct.
Now what if we are searching for 60?
It should give us false because it's not there.
And yes, you can see we are getting false.
What if we are searching for one?
It should give us true.
So we get true?
Yes.
So our function is working.
Now let's go ahead and walk through the code.
Let's take an example.
Let's say we are searching for the value 40 or let's say we are searching for three.
All right.
So let's say we are searching for the value three.
Now let's take this example and walk through the code which we have just now written.
All right.
So we have this matrix.
And the value for which we are searching is three.
Now we are calling the function.
So we come over here.
Now let let me just write parallelly along with this.
So we find the number of columns over here.
Now we see we have seen over here below that there are four columns right.
So we have one two, three four.
So the number of columns is equal to four.
So let's just write that over here.
And the number of rows.
What about the number of rows.
Let's check that over here.
We have 123 and four.
We have four rows right.
So these four rows.
So the number of rows is also equal to four.
And then we come over here.
Top is equal to zero and bottom is going to be equal to three because rose is four right.
So bottom is three and top is equal to zero.
And then we see that zero less than equal to three.
That's true three.
So we come inside the while loop and we're going to calculate middle.
Middle is going to be zero plus three divided by two.
And then we have flooring it.
So that's equal to one.
So middle is equal to one.
Now in the row middle that is matrix at one right.
So we are going to take the zeroth index element.
And we are checking if target is less than this.
So let's take a look at it.
So we have the row one which is this row over here.
And the zeroth index we have five.
So is target less than five.
Yes target is three.
So target is less than five right.
So yes that's true.
So we go ahead and over here we are setting bottom is equal to middle minus one which is equal to zero.
So bottom is equal to zero.
Again we come over here top is zero and bottom is zero and zero equal to zero.
So that's true.
So we come inside and we calculate again middle right.
So we calculate middle again.
Now at this point.
Middle is going to be equal to zero plus zero divided by two, which is zero itself.
Right?
So middle is zero.
Now again we are checking matrix at zero.
That is we are taking the array at the index zero which is 1234.
So we have the array 1234.
So let me just write this over here.
So this over here matrix at zero is the array 1234.
Now we are taking the element at the zeroth index which is one and target is three.
So is three less than one.
No that's false.
So this is false.
See.
Now we are checking over here is target greater than matrix at zero which is this array at columns minus
one.
So columns is equal to four four minus one is three which is this index.
Over here.
Now is three.
The target is three.
Which is the target greater than four.
No that's also false.
So we don't go ahead over here.
And then we come to this part and then we break out.
All right.
So at this point middle is equal to zero.
And we have broken out.
Now top is zero and bottom is also equal to zero.
All right.
Now once we come out of this while loop over here we check if top is greater than bottom.
We have seen that top is zero and bottom is zero.
So top is not greater than bottom.
So we don't return false.
All right.
So that means we have identified the row in which we can have the target value.
Again it's not necessary that the target value is there in that row.
But if it is there in the matrix it can only be there in that particular row.
Now we come over here we said left is equal to zero.
And we said right is equal to columns minus one which is equal to three.
So left is pointing over here this is index 012 and three.
And right is pointing at index three.
Now it's just a normal binary search right.
So we are having the variable mid value over here.
And we calculate mid value which is left plus right divided by two.
So zero plus three by two.
That gives us.
And when we floor it it gives us one.
So middle is pointing to index one.
Now we are checking if target is equal to middle.
And we see that target was three right.
So target is not equal to the value at middle.
So we see that target is greater than this value.
So we are going to change the left pointer.
The left pointer is changed to middle plus one.
So left is pointing to index two.
Right is pointing to index three.
So we calculate the new middle which is two plus three divided by two.
And then we are flooring it.
So middle is also going to going to point at index two.
And we see that target is equal to the matrix at row zero and the middle value which is two.
So we have found the target value and we will return true.
And this is how the code works.
All right.
Now let's take a quick look at the space and time complexity of our solution.
Now in the function which is search index search in matrix you can see that over here we are implementing
once the binary search to identify the relevant row right.
This part over here.
So over here we are going to do O of log m operations where m is the number of rows.
All right.
And then once this is done, we are also doing one more binary search in this part.
Which is the normal binary search, which you have seen previously, to identify whether the target
value is there in the row that we have identified.
Now this is going to be doing O of log n operation, where n is the number of columns.
Right.
Because in one array they are going to be n elements.
So that's why we can say that the time complexity of this solution is O of log m plus log n and log
m plus log n is nothing but log m n.
So log n plus log n is log m into n.
That's why the time complexity of this solution is o of log m n, and you can see that we are not using
any extra space.
So the space complexity is equal to O of one.
Or this solution runs in constant space.