0

I've found the answer: How do I search for a number in a 2d array sorted left to right and top to bottom?

Rectangular Young tableau is a m x n matrix with every column in increasing order from up to down and every row in increasing order from left to right.

Is there efficient algorithm which can search a target in this matrix and tell me the position of this target or not found.

In fact, we can always do binary searchs in first column/row and last column/row such that in O(log mn) to restrict the original matrix to a submatrix with all elements in first row and first column smaller than target and all elements in last row and column larger than target. Or we have already been able to tell the target not in the matrix or have found it in these four binary search.

maplemaple
  • 1,297
  • 6
  • 24
  • Are you querying once per matrix or many times? That is: how much preprocessing time can you tolerate? Do you have a sense of the size of your input data? – Richard May 29 '19 at 17:08
  • @Richard I just want to solve this problem by some clever method. The most naive method is doing binary search very line ``O(m log n)`` for m <= n. I'm thinking whether there is faster method. I've found the answer and I've posted in the top. – maplemaple May 29 '19 at 17:12
  • Developing a clever method requires answering those questions. A method is only clever if it's suited to the use case. For instance, there are _O(1)_ solutions to this problem for particular combinations of input and use. However, it sounds like you want a general solution for inputs with low reuse. For that scenario the answers you link to are probably alright. – Richard May 29 '19 at 18:01

0 Answers0