4

Possible Duplicates:
Given a 2d array sorted in increasing order from left to right and top to bottom, what is the best way to search for a target number?
Search a sorted 2D matrix

A time efficient program to find an element in a two dimensional matrix, the rows and columns of which are increasing monotonically. (Rows and columns are increasing from top to bottom and from left to right).

I can only think of binary search, if the 2D array was sorted.

Community
  • 1
  • 1
abhi4eternity
  • 448
  • 3
  • 8
  • 19
  • Even when monotonically increasing as opposed to sorted, a kind of binary search can be done, but as pointed out there are better ways to proceed. – Jérémie Aug 13 '10 at 14:03

4 Answers4

15

I posed this problem as homework last semester, and two students, which I had considered to be average, surprised me by coming up with a very elegant, straightforward, and (probably) optimal algorithm:

Find(k, tab, x, y)
  let m = tab[x][y]

  if k = m then return "Found"
  else if k > m then
    return Find(k, tab, x, y + 1)
  else
    return Find(k, tab, x - 1, y)

This algorithm eliminates either one line or one column at every call (note that it is tail recursive, and could be transformed into a loop, thereby avoiding the recursive calls). Thus, if your matrix is n*m, the algorithm performs in O(n+m). This solution is better than the dichotomic search spin off (which the solution I expected when handing out this problem).

EDIT : I fixed a typo (k became x in the recursive calls) and also, as Chris pointed out, this should initially be called with the "upper right" corner, that is Find(k, tab, n, 1), where n is the number of lines.

Jérémie
  • 1,353
  • 9
  • 19
  • Beat me by seconds! By the way, the second recursive call to Find needs to be capitalized. – Niki Yoshiuchi Aug 13 '10 at 14:03
  • What's z? Should that be m again? – Chris Aug 13 '10 at 14:04
  • @Chris: Yes "z" should "m" again, I corrected this just as you were reading. @Niki: ha ha ha, you just want me to edit my post enough so the timestamp will change and it'll seem like I modified my answer after reading yours :-D – Jérémie Aug 13 '10 at 14:05
  • I'll make you a deal, you edit yours, I'll edit mine :). – Niki Yoshiuchi Aug 13 '10 at 14:06
  • And also just for clarification am I correct in thinking that you start by Calling Find with x,y being the top right of the matrix (ie x starts at max and y at min)? – Chris Aug 13 '10 at 14:06
  • This is not an optimal algorithm. See the answers to this version: http://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom This algorithm performs significantly worse than the optimal solution for any matrix with one dimension significantly longer than the other. – Jeffrey L Whitledge Aug 13 '10 at 14:15
  • @Jeffrey: yes the solution you suggest in that post is the straightforward adaptation of dichotomic search I expected my students to give. O(N+M) does imply that this is an iffy choice if one of dimension is significantly longer than the other---assuming for instance N << M, you'd do better to perform dichotomic search on each of the lines or columns to get O(N log(M)). – Jérémie Aug 13 '10 at 14:28
  • Can you elaborate what tab, x, and y represent in the parameters? A student here myself hence the simplistic question – Hamza Jan 18 '23 at 08:58
7

Since the the rows and columns are increasing monotonically, you can do a neat little search like this:

Start at the bottom left. If the element you are looking for is greater than the element at that location, go right. If it is less go up. Repeat until you find the element or you hit an edge. Example (in hex to make formatting easier):

1 2 5 6 7
3 4 6 7 8
5 7 8 9 A
7 A C D E

Let's search for 8. Start at position (0, 3): 7. 8 > 7 so we go right. We are now at (1, 3): A. 8 < A so we go up. At (1, 2): 7, 8 > 7 so we go right. (2, 2): 8 -> 8 == 8 so we are done.

You'll notice, however, that this has only found one of the elements whose value is 8.

Edit, in case it wasn't obvious this runs in O(n + m) average and worst case time.

Niki Yoshiuchi
  • 16,883
  • 1
  • 35
  • 44
0

Assuming I read right you are saying that the bottom of row n is always less than the top of row n+1. If that is the case then I'd say the simplest way is to search the first row using a binary search for either the number or the next smallest number. Then you will have identified the column it is in. Then do a binary search of that column until you find it.

Chris
  • 27,210
  • 6
  • 71
  • 92
0

Start at (0,0)

  • while the value is too low, continue to the right (0,1), then (0,2) etc.
  • when reaching a value too high, go down one and left one (1,1)

Repeating those steps should bring you to the target.

James Curran
  • 101,701
  • 37
  • 181
  • 258
  • This won't work. If you look at my example matrix, try searching for 3. You'll go (0,0):1 > (1,0):2 > (2,0):5 v (1, 1):4 v (0, 2): 5 and the next move will take you off the edge (which I assume would be the "not found" condition). – Niki Yoshiuchi Aug 13 '10 at 14:17