Searching a 2D Sorted Matrix Part III
October 13, 2010 in divide and conquer
Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,
Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]
Test Data Sets:
I created three test input files (Download all of them below) by myself for testing and studying purposes. Each file contains multiple test cases. The easy input contains 15 test cases, with M and N = 10, K = 50. The hard input contains 23 test cases, but with M and N = 100, K = 100,000. The performance input has M and N = 1000, and K = 1,000,000.
Here are the run times of the five different algorithms using the performance input data set.
Binary Search: 31.62s Diagonal Binary Search: 32.46s Step-wise Linear Search: 10.71s Quad Partition: 17.33s Binary Partition: 10.93s Improved Binary Partition: 6.56s
As you can see from the results above, the Improved Binary Partition method is clearly the winner here.
Each test case starts with two integers, M and N. M is the number of rows and N is the number of columns of the matrix. The subsequent M lines would be the contents of the matrix in row-order. Each line would contain N integers separated by a single space. Following that is a blank line, with an integer, K, the total number of targets to be searched in the matrix. The next line contains K integers in one line, each of them separated by a single space. After that is a blank line. Then followed by the next case. M=0 and N=0 and K=0 indicates that there are no more inputs.
For each test case, output “Test case #x“, where x is the test case number starting from 1. After that you should have K lines, each line telling if the target is found in the matrix or not. If the target is found in the matrix, output “Target y found at (i,j)”, where y is the searched element, while i and j are the row and column number of the found element respectively. If the target could not be found, then output “Target y not found”. The next test case should be separated by a blank line from the above test case.
1 1 1 3 0 1 2 1 2 -1 3 8 -2 -1 0 1 2 3 4 5 0 0 0
Test case #1 Target 0 not found Target 1 found at (1,1) Target 2 not found Test case #2 Target -2 not found Target -1 found at (1,1) Target 0 not found Target 1 not found Target 2 not found Target 3 found at (1,2) Target 4 not found Target 5 not found
A variation of this problem had been asked in Amazon interviews:
2D Matrix(n * n) of positive and negative numbers is given. Matrix is sorted rowwise and columnwise. You have to return the count of -ve numbers in most optimal way.