Suppose we are given an n by n matrix M of integers, where each row is sorted in increasing order from left to right and each column is sorted in increasing order from top to bottom, and given an integer x. We want to determine if x is present in M.
(a) It is straightforward to do this in O(n log n) time. Describe such an algorithm.
(b) Can you do better? Explain your solution