Search in a row wise and column wise sorted matrix | GeeksforGeeks

[@egor.okhterov]

It feels like this method is suboptimal, because, for example, if the matrix is 1 x n or n x 1 then we could do a binary search instead of linear search.

[@prateekrai665]

Awesome explanation. :)

[@mitakshichandna172]

why didnt we use else if instead of second if statement?:(

[@ankitsharma8221]

Awesome explanation!

[@jeevanadhikari1588]

Can you please show the derivation of time complexity for this algorithm to O(n)

[@rajvijay3276]

In the worst case , starting from the top right corner , element will be found at bottom left corner. No. of comparisons you do is going to be n. Hence O(n).

[@ravindraPratapsingh7]

In the worst case if 32 (in given matrix) need to be searched (left most, down most element). The number of comparisons will be : n (row traversal) + n (column traversal) = 2n , So Time complexity can be stated as O(n).

[@pranavamjks]

As mentioned by others, complexity here stands for the number of comparisons the algorithm make. Either one row or column gets deleted at each step. So either row count or column count gets decreased by one at each step. This essentially means that we will have, at the maximum, n+m number of steps, which is essentially the number of comparisons.

[@ksuman-in]

when finding the first column of the value then not find the accurate value for example I'm finding 15 then not found.

[@SaurabhKumar-th3gm]

Can We start from bottom left most element.

[@amarbathwal1226]

Saurabh Kumar yes u can

[@harishkulkarni7244]

Yes but the algorithm would change, if e < x then you would move towards right since the elements on right are bigger. If e > x, then you would move up since the elements on up are smaller. But the implementation would be more cumbersome I guess.

[@gavin8535]

Or we can start at bottom left.

[@lifecodesher5818]

yaarr conditions sahi kro apni

[@lifecodesher5818]

this condition is wrong i guess it should be opposite

[@subhashchaudhary7003]

Improve sound quality ... It's irritating, sounds when you stop and start back

[@anubhavc4026]

Wrong method. Try finding 33 in your example.

[@rajvijay3276]

Please try tracing it, It's right. 40->30->35->25->29->33

[@pramodkumarkar8153]

working correctly for 33 also.