Searching a 2D Sorted Matrix Part III

October 13, 2010

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]

Note:
This is Part III of the article: Searching a 2D Sorted Matrix. Please read Part I and Part II for more background information.

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
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.

Input:
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.

Output:
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.

Sample Input:

```1 1
1

3
0 1 2

1 2
-1 3

8
-2 -1 0 1 2 3 4 5

0 0
0
```

Sample Output:

```Test case #1
Target 1 found at (1,1)

Test case #2
Target -1 found at (1,1)
Target 3 found at (1,2)
```

Further Thoughts:

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.

VN:C [1.9.22_1171]
Searching a 2D Sorted Matrix Part III, 4.7 out of 5 based on 10 ratings

12 responses to Searching a 2D Sorted Matrix Part III

1. Hi, what does "-ve numbers" mean? I don't quite understand.

VA:F [1.9.22_1171]
-2
2. "-ve" numbers mean "negative" numbers.

VA:F [1.9.22_1171]
-1
3. // Printed coordinate (i, j) specifies the LR
// boundary of the -VE area.

public static listVEMatrix(int[][] A) {
int i = 0;
int j = A[0].length;
while (i < A.length && j >= 0) {
if (A[i][j] < 0) {
System.out.println(i + " " + j);
i++;
else j–;
}
}

VA:F [1.9.22_1171]
+1
4. Dude , of all the explanations I have seen of this problem , this is clearly the best , fantastic work !!
Thank You

VA:F [1.9.22_1171]
0
5. Very specific and detailed explanation, and with example and comparison which makes it really easy to understand. Thanks!

VA:F [1.9.22_1171]
0
6. Hi, first of all thank you for your time and effort. I would like to ask a question relating to the quad partitioning. How did you decide on worst case array configurations (the timings seem to agree with your calcs.) I have tried myself, but cant get this algo to perform worse than O(logn).

Thanks!

VA:F [1.9.22_1171]
0
7. Hi 1337c0d3r
You are getting more run-time with “Diagonal Binary Search” as compared to normal Binary search.It is supposed to be less, no ? Can you please help here.

VA:F [1.9.22_1171]
0
8. Do you have the algorithm for the variation of this problem ?

VA:F [1.9.22_1171]
0
9. Your analysis of Quad Partition is against intuition. If every step reduces the size of problem by 1/4, eventually the complexity should be logarithmic, just an extension to 1D binary search.

The recursion formula is not convincing: T(n) = 3T(n/2) + c, which I believe is wrong.
Something makes more sense would be T(n) = 3T(n/4) + c.

VA:F [1.9.22_1171]
0
10. Hello. I just have a solution to do at most binary search, can you take a look?
http://www.laurashawn.net/?p=10911

Basically:
1.search left column
smaller than first, false
in middle, do another binary search and get result
bigger than last, then search the last row, and do another binary search as needed.

VN:F [1.9.22_1171]
0
11. After one night of sleep, I think only two binary search is enough. Just first search the array from left and button together (smallest to biggest), then you know which row or column to search, do another binary search and you are done!

For 3D cubic, same idea, just need 3 binary search, first determine with 2D matrix to search, so on.

as 1 D array, you need 1 search, 2D, you need 2, 3D need 3, XD need x search. I am glad I get to the button of this questions by myself.

VN:F [1.9.22_1171]
0
12. Oh, Shit. I found my algorithm is wrong. However, it passed OJ! The test case doesn’t cover everything.

VN:F [1.9.22_1171]
-1