Searching a 2D Sorted Matrix Part III

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

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

Attachments:
» Download Easy Input
» Download Easy Output
» Download Hard Input
» Download Hard Output
» Download Performance Input

Further Thoughts:
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.

VN:F [1.9.22_1171]
Rating: 4.8/5 (20 votes cast)
Searching a 2D Sorted Matrix Part III, 4.8 out of 5 based on 20 ratings

19 thoughts on “Searching a 2D Sorted Matrix Part III

  1. Anonymous

    // 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]
    0
  2. Anurag Atri

    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]
    +2
  3. Snowy101

    Very specific and detailed explanation, and with example and comparison which makes it really easy to understand. Thanks!

    VA:F [1.9.22_1171]
    +1
  4. Pingback: Searching a 2D Sorted Matrix Part III | 口├人人│의 Blog

  5. interested

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

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

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

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


    public static int searchNegative(int[][] matrix){
    int x=0, y=matrix[0].length-1;
    int cnt = 0;
    while(x>=0 && x=0 && y<matrix[0].length){
    if(matrix[x][y] <= 0){
    cnt += y+1;
    x++;
    }else{
    y--;
    }
    }
    return cnt;
    }

    VN:F [1.9.22_1171]
    +3
  10. theOtherWC

    Aha, the Amazon question is tricky, because it asks you to count rather than return. If it’s the latter, then we can only have O(mn) algorithms.

    VA:F [1.9.22_1171]
    0
  11. Pingback: LeetCode | techinterviewsolutions

  12. Pingback: LeetCode | Technical interview solutions

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*