Given an M * N matrix in which each row and each column is sorted in ascending order, write a method to find an element.
O(N + M) solution
By traversing matrix from upper right to lower left, we can solve this problem in O(N + M) time.
O((log N)2) solution
Searching a 2D Sorted Matrix Part II – LeetCode
As you can see, the run time complexity of this extreme case is O(lg n)2, which turns out to be even less than O(n).