Hi everyone.
Let's do this question right.
An efficient algorithm that searches for a value target in an m into n integer matrix.
This matrix has the following properties.
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer in the previous of the previous row.
If the value is there in the matrix, return true, else false.
Now first let's think about what is a matrix.
Now a matrix is nothing but a 2D array.
So that's just an array where each element is an array.
So let's take an example.
Let's say this is the matrix which is given to us.
So you can see that this is nothing but an array with three elements.
And each element is an array itself.
Now we can visualize this like this also.
So typically a matrix is drawn out like this.
Now the values in this array one, two, three are these three values over here.
And then we have four five, six over here.
And we have 789 over here.
So this is a matrix which is given to us.
Now in this matrix we have to search for a value.
Let's say target is given as five.
Now because five is there in this matrix.
We have to return true.
If the target value, let's say was ten, then we would have to return false because it's not there
in the matrix which is given to us.
So this is the question.
And then remember we are asked to write an efficient algorithm.
All right.
So that's the catch over here.
And then also let's take a look at the properties which is given.
It's mentioned over here that integers in each row are sorted from left to right.
So from left to right the integers are sorted.
And then it's mentioned that the first integer of each row is greater than the last integer of the previous
row.
So over here you have three.
This would be greater than three, which is four.
And if this is six, whatever comes over here has to be greater than six.
It can be seven or 70 or 17 whatever.
But it has to be greater than six.
So that is what is mentioned in the question.
So let's go ahead and write a few test cases to think about this question.
We have already seen one test case.
If this is the matrix which is given to us, and if the target is equal to five, then we have to return
true because the value five is there in the given matrix.
Now, if the target was equal to ten, then we would have to return false again.
If the matrix is empty right?
Then if there is a target, for example something like one, then we have to return false because we
can see that the matrix is empty.
Therefore, one is not present in the matrix which is given to us.
So we have understood the question.
And remember over here you can see that it's mentioned that the data is sorted.
And we are asked to write an efficient algorithm.
So these are hints.
So we know that whenever the data is sorted we can make use of the binary search algorithm.
So try to think how you can make use of the binary search algorithm to write an efficient solution to
this question.