Write an efficient algorithm that searches for a value in an

nxmtable (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.62sDiagonal Binary Search:32.46sStep-wise Linear Search:10.71sQuad Partition:17.33sBinary Partition:10.93sImproved 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:

Searching a 2D Sorted Matrix Part III,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.

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

-1"-ve" numbers mean "negative" numbers.

+1// 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–;

}

}

0Dude , of all the explanations I have seen of this problem , this is clearly the best , fantastic work !!

Thank You 🙂

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

+1Pingback: Searching a 2D Sorted Matrix Part III | 口├人人│의 Blog

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!

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

0Do you have the algorithm for the variation of this problem ?

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

0I agree.i think so too..

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

0After 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. 😉

0Oh, Shit. I found my algorithm is wrong. However, it passed OJ! The test case doesn’t cover everything. 🙁

-1public 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;

}

+3Aha, 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.

0Pingback: LeetCode | techinterviewsolutions

Awesome answer to this frequently asked question. Thank you !

0Pingback: LeetCode | Technical interview solutions