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

Suppose we are given an n by n matrix M of integers, where each row is sorted in increasingorder from left to right and each column is sorted in increasing order from top to bottom, andgiven 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