O(m+n)
We can use a variation of linear search begining from top right or bottom left corner and we can move left or bottom( if we start from top right corner) after making comparisons.
Ex. searching for a number say 4 occurs in this way starting from top right corner. blue cells is the path to reach 4.
1 |
3 |
5 |
8 |
4 |
9 |
10 |
12 |
6 |
13 |
14 |
15 |
worst case occurs when number to be searched is at opposite end of matrix , in that case m+n steps have to be taken to reach the opposite side.