Question

In Java Describe an algorithm that given a matrix described below determines whether matrix contains a value k. The input matrix A[1...n, 1...n] has all rows and columns arranged in an non-descending order A[i, j] < A[i, j+1], A[j, i] < A[j + 1, i] for all 1 < i < n and 1 < j < n

Answer 1

One possible solution using divide and conquer approach would be:

Let’s start our search from the top-right corner of the array. There are three possible cases.

1. The number we are searching for is greater than the current number. This will ensure, that all the elements in the current row is smaller than the number we are searching for as we are already at the right-most element and the row is sorted. Thus, the entire row gets eliminated and we continue our search on the next row. Here elimination means we won’t search on that row again.
2. The number we are searching for is smaller than the current number. This will ensure, that all the elements in the current column is greater than the number we are searching for. Thus, the entire column gets eliminated and we continue our search on the previous column i.e. the column at the immediate left.
3. The number we are searching for is equal to the current number. This will end our search.

Since, at each step, we are eliminating an entire row or column, the time complexity of the search becomes O(n).

Algorithm

Let x = element we’re trying to search for in the matrix,
….e = current element we’re processing in the array.

1) Start with top right element.
2) Loop: compare this element e with x
…i) if e = x, then return position of e, since we found x in the given matrix.
…ii) if e > x then move left to check elements smaller than e (if out of bound of matrix, then break and return false)
…iii) if e < x then move below to check elements greater than e (if out of bound of matrix, then break and return false)
3) repeat the i), ii) and iii) until you find the element or return false

The corresponding code