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]

Google this problem and you will see that a lot of sites have posted this problem before me. So why another blog post?

I have read through forums, blog posts, and go through each comment people made. Surprisingly, most people had answered this question incorrectly. Especially the run time complexity part. They just put down the recurrence formula and “guess” the complexity. It just don’t work like that. To save you from frustration, I decided to post all possible solutions and my in-depth analysis here.

The most efficient solution is surprisingly easy to code. Its run time analysis is also easy to prove. It is also surprisingly easy to make incorrect assumptions if you are not careful.

**Note:**

For the sake of run time complexity analysis, we will assume that the matrix is a square matrix of size *n* x *n*. Your algorithm should work on matrix of size *m* x *n* though.

**Hint:**

If you are choosing a place to start from, try the top right corner. Or the bottom left corner.

**Binary Search Solution:**

Most people will observe the keyword “sorted”, which no surprise that the idea of applying Binary Search to each row (or to each column) came up immediately. As each row takes *O*(lg *n*) time to search, and there are a total of *n* rows, we are able to do it in *O*(*n* lg* n*) time. Of course, your interviewer will tell you that this is not a good enough solution. In fact, this is the first trap that you should look out for! Do not confine yourself into thinking that binary search is the only way to solve this problem.

**Incorrect Solution:**

Here is another trap that most people will fall into if they are not careful enough. This is based on an incorrect assumption that if the target element falls between two numbers in the first row, then the target element must be within that two column. If not, then the target element does not exist.

Assume that you are searching for **9**. You scan through the first row and see that **9** appears between **7** and **11**. Therefore, apply Binary Search on these two columns (highlighted in yellow below). This is wrong, try to look for **10** in the matrix. **10** does not belong to any of those two columns.

**9**but failed to search for

**10**.

What if we do the same to the rows too? That is, since **10** is between **3** and **10**, we apply binary search both to the two rows and two columns (as highlighted in yellow below). Finally, **10** could be found now. Although it seems to work in this example matrix, this is an incorrect solution. Coming up with a counter example is left as an exercise to the reader.

**9**and

**10**now. Is this solution correct? Try to come up with a counter example.

**Diagonal Binary Search (Still not there yet):**

Still not giving up, you keep on brainstorming on how you can do a Binary Search in a more efficient manner.

How about we traverse the matrix diagonally starting from the top right corner? We will call this method the *Diagonal Binary Search* method. You may also start from the bottom left corner, it doesn’t matter.

Assume that our target is ’10’. We start from the top right corner, which contains the element **15**. Since **10** is less than **15**, we could eliminate the entire column from consideration as illustrated below (Areas that are eliminated are colored in gray). This follows from the rule that the column is in sorted order.

We apply binary search from element **1** to **11** on the first row. Since **10** is not found, we proceed to the next diagonal step, which is **12**. **10** is less than **12**, therefore we do a binary search from **2** to **8** across the second row. Since **8** is less than **12**, you could skip doing a binary search anyway. Now, the eliminated areas are shown below. You could see that we continue next with element **9** and do a binary search across the third column from **14** to **23**. Eventually we will find **10** following that.

As we traverse diagonally, there’s one less item to search for either across the row or column. Therefore, the run time complexity can be written as:

T(n) = lgn+ lg (n-1) + lg (n-2) + ... + lg (1) = lgn(n-1)(n-2)...(1) = lgn!

Compared to the previous method, this is a tiny bit of improvement over the last method. Proof of lg *n*! is less than *n* lg *n* is left as an exercise to the reader.

**» Continue reading Part II: Searching a 2D Sorted Matrix.**

http://geeksforgeeks.org/?p=11337

+1Hi, I like your solution!

I am wondering if it is possible to have another solution

My impression is that the diagonal (top-left to bottom-right) elements are greater than the entire submatrix (which starts at (0,0) and ends at that diagonal element) they lie in.

Say you’re looking for element x

Look for 2 diagonals (top-left to bottom-right) such that x>=d1 and x<=d2. Well if x==d1 or x==d2 we're done.

Otherwise we have to search between these 2 diagonals. Let me try to draw it:

This is the matrix:

– – – |

– – – |

– – 9 |

| | |17

If we are looking for 10, we know it is bw 9 and 17 (on the diagonals). So we search only in the rows and column I marked with pipe "|".

The runtime would be sth along: 2*log(d2) + 2*log(d2-1) + … 2*log(d1)

0@Adrian M, I think you are wrong on “Otherwise we have to search between these 2 diagonals”. A counter example: switch the positions of “17” and “18” in the matrix above, and try to search “17”.

+2Pingback: You are given an MxN matrix of numbers, with the property that numbers increase as you go down each column, and as you go right on each row. How can you efficiently check whether a given number is in the matrix? - Quora

What is the running time of this?

I think it should be O(M+n) or O(N) ? Since at every step we are just removing a row or column. Worst case the element is at lowest left corner if we are starting from top right. Total traversal is m + n. How is it log n!?

+4In your approach, the binary search on each row may not be necessary. The solution provided by @rajiv takes only O(n).

0I agree with Kapil. The running time of diagonal binary search is O(N). in each step, we either go down or go left, so we can move as many as N + N steps to find a solution or reach a border.

0never mind…. i didn’t fully understand diagonal binary search before post.

0Hi,

I have the following question, if you can an efficient algorithm to solve the problem, then do mail me:

if there is a matrix A[][] of order m and another matrix B[][] of order n such that (m>n) you have to find the occurance of matrix B[][] in matrix A[][].

A[5][5]=1,2,3,4,5

5,4,1,9,7

2,1,7,3,4

6,4,8,2,7

0,2,4,5,8

B[3][3]=1,9,7

7,3,4

8,2,7

this matrix B exist in A.

0hello Is this solution right or wrong? http://geeksforgeeks.org/?p=11337

0I think the author mistook one thing. When calculating, it should be

(logn + 1) + (log(n-1) +1) + (log(n-2) + 1) …, he/she missed the 1 for checking diagonal element.

In traditional way, after each compare, we simply move 1 step, which yields (1+1)+(1+1) + …

given an N*N grid, the author’s approach is N+logN!, while the traditional one is just 2N.

+2Pingback: kkbox 面試 | taikerliang

Pingback: [leetcode] Search a 2D Matrix | 二维矩阵找其中某个element的位置 | Lexi's Leetcode solutions

Pingback: Searching a 2D Sorted Matrix - JavaScript - GeniusCarrier

Correct me if I’m wrong:

(1) Regarding the algorithm that does binary search along the diagonal line, we can do divide and conquer in 2 smaller (n/2)x(n/2) grids. So the recurrence will be roughly T(n) = 2T(n/2) + logn, where logn is used to do binary search. From master’s theroem we see T(n) = O(n).

(2) Regarding the algorithm that eliminates either one column or one row by comparing target with the right uppermost element, this is also an O(n) algorithm.

0thanks for posting so clear explanation .keep on doing this job!

0Isn’t the time complexity O(n) and not O(log n!)?

While the algorithm is efficient, it seems complex.

Following is a simpler one, takes O(n)

e is the element at index

x is the element we’re searching for.

1. Go to topmost right corner.

2. If ex, go left

Repeat until you go out of bounds.

Source : geekforgeeks

0The complexity is log(n!), which by Stirling’s approximation is equivalent to:

log(n^n * e^(-n))

= log(n^n) + log(e^(-n))

= nlogn – n

= n(logn – 1)

= nlogn

What am I missing here?

0The author’s algorithm is right. And I think the run time analysis is also right to this algorithm. The solution provided by @rajiv seems easier to understand and better.

0Pingback: find iso-cost points on a 3d grid efficiently with minimum costing of points - DL-UAT

Pingback: [NineChap 2.1] Binary Search | 海淘好deal

Pingback: LeetCode 240: Search a 2D Matrix II | helloyuan

Pingback: Report all occurrences of an element in row wise and column wise sorted matrix in linear time - Techie Delight