Bifalgorithm post

So guys, today we are going to learn another matrix related question. The question is that we have a matrix of size m cross n and a target element and we need to find this target element inside this matrix. Okay. So for this question, the very basic brute force approach that we can think of is to traverse the entire matrix like this and then keep on comparing the matrix elements with the target. And once we find it, we will simply return. Okay. But as it is mentioned in the question, you can see over here, as it is mentioned in the question that we need to solve this in log m cross n time complexity. So for this particular reason, what we are going to do, we will try to implement binary search here. We will try to implement binary search here. Now let's see how we can apply binary search. So if you observe carefully, you will notice that each row of this matrix is sorted. This is also sorted, this is also sorted, and this is also sorted. directly apply a binary search on every row blindly. No. For example, if this is the row and my target is 3. Now I can clearly see that my target is never going to lie in this row. So is there any point of applying binary search in this row? Obviously not. Same for this particular row. I know my target is 3 and I can clearly see that my target is not going to lie in this particular row. So is there any point of applying binary search here? Obviously not, right? So before applying binary search blindly on every row, first we will check whether my target element can possibly lie in that row or not. And if yes, only then we will apply the binary search in that row. Okay, so I hope you got the logic now. Now let's see how we can code this thing. So here you can see we are traversing row wise and here we have a check before applying binary search here we are checking is my target element greater than equal to the first element of that row and less than equal to the last element of that row or not. For example, if these are the row element and my target is three. So I am checking is my target element greater than equal to the first row, first element of that row and less than equal to the last element of that row or not. If this condition is true, it means there might be chances that my target will lie in this particular row. Okay. So if this condition is true, I am simply applying binary search here, like the general binary search as we usually do calculating the low and high pointers and then finding the mid value and comparing the target with the mid. Okay. And then keep on adjusting the low and high pointers. I'm assuming that you know the binary search, right? So the main thing is this before applying binary search blindly on every row, we are checking is my target element can possibly lie in that row or not. If yes, if that if the condition is true, then only we are applying binary search in that row. So that's it for today. Share this deal with your friend who is also learning DSA and I will see you in the next video with another question.

So guys, today we are going to learn another matrix related question. The question is that we have a matrix of size m cross n and a target element and we need…