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

Question

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

A temporary effective program for finding an element in a two-dimensional matrix whose rows and columns are monotonically increasing. (Rows and columns grow from top to bottom and 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, who I considered average, surprised me by coming up with a very elegant, simple and (possibly) 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 row or one column for each call (note that it is a tail recursive and can be converted to a loop, thereby avoiding recursive calls). So, if your matrix is ​​n * m, the algorithm executes in O (n + m). This solution is better than a dichotomous search backing off (which is the solution I expected when distributing this problem).

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

Answer 2

As rows and columns grow monotonously, you can do a neat little search like this:

Start at the bottom left. If the item you are looking for is larger than the item in this place, go right. If it will be less. Repeat until you find the item or you have not reached the edge. Example (in hexadecimal format to simplify formatting):

 1 2 5 6 7 3 4 6 7 8 5 7 8 9 A 7 ACDE 

Let search 8. Start from position (0, 3): 7. 8> 7, so go right. Now we are in (1, 3): A. 8 <And so we go. On (1, 2): 7, 8> 7, so we go right. (2, 2): 8 → 8 == 8, so we are done.

However, you will notice that he found only one of the elements whose value is 8.

Change, if this is not obvious, this is done in the O (n + m) average and worst case.

Answer 3

Assuming I'm right, you say that the bottom line of line n is always less than the top of line n + 1. If so, then I would say that the easiest way is to search for the first line using a binary search of either the number or the next smallest numbers. Then you determine the column it is in. Then do a binary search for this column until you find it.

Answer 4

Start with (0,0)

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

Repeating these steps should lead you to your goal.