Algorithm: efficient way to search an integer in a two dimensional integer array?

Question

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.

Answer 1

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 you are matrix is n*m, the algorithm performs in O(n+m). This is solution is better than the adaptation of dichotomic search (which was the expected solution when I handed 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.

Answer 2

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.

Answer 3

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.

Answer 4

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.