2D sorted array. Element search.

A 2D integer array is such that each row and column in it is in ascending order. How will you search for a specific element in it ?

Clue: A simple implementation in O(m+n) can be done.  

A more complex recursive approach using diagonals as breakpoints of recursion can also the thought off. Basically, recursively spitting a matrix into sub-square matrices for the search on the diagonal. Am yet struggling with the complexity analysis part.