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?

Question

I was recently given this interview question and I'm curious what a good solution to it would be.

Say I'm given a 2d array where all the numbers in the array are in increasing order from left to right and top to bottom.

What is the best way to search and determine if a target number is in the array?

Now, my first inclination is to utilize a binary search since my data is sorted. I can determine if a number is in a single row in O(log N) time. However, it is the 2 directions that throw me off.

Another solution I thought may work is to start somewhere in the middle. If the middle value is less than my target, then I can be sure it is in the left square portion of the matrix from the middle. I then move diagnally and check again, reducing the size of the square that the target could potentially be in until I have honed in on the target number.

Does anyone have any good ideas on solving this problem?

Example array:

Sorted left to right, top to bottom.

1 2 4 5 6  
2 3 5 7 8  
4 6 8 9 10  
5 8 9 10 11  

Answer 1

A. Do a binary search on those lines where the target number might be on.

B. Make it a graph : Look for the number by taking always the smallest unvisited neighbour node and backtracking when a too big number is found

Answer 2

Binary search would be the best approach, imo. Starting at 1/2 x, 1/2 y will cut it in half. IE a 5x5 square would be something like x == 2 / y == 3 . I rounded one value down and one value up to better zone in on the direction of the targeted value.

For clarity the next iteration would give you something like x == 1 / y == 2 OR x == 3 / y == 5

Answer 3

I would use the divide-and-conquer strategy for this problem, similar to what you suggested, but the details are a bit different.

This will be a recursive search on subranges of the matrix.

At each step, pick an element in the middle of the range. If the value found is what you are seeking, then you're done.

Otherwise, if the value found is less than the value that you are seeking, then you know that it is not in the quadrant above and to the left of your current position. So recursively search the two subranges: everything (exclusively) below the current position, and everything (exclusively) to the right that is at or above the current position.

Otherwise, (the value found is greater than the value that you are seeking) you know that it is not in the quadrant below and to the right of your current position. So recursively search the two subranges: everything (exclusively) to the left of the current position, and everything (exclusively) above the current position that is on the current column or a column to the right.

And ba-da-bing, you found it.

Note that each recursive call only deals with the current subrange only, not (for example) ALL rows above the current position. Just those in the current subrange.

Here's some pseudocode for you:

bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)

if (minX == maxX and minY == maxY and arr[minX,minY] != value)
    return false
if (arr[minX,minY] > value) return false;  // Early exits if the value can't be in 
if (arr[maxX,maxY] < value) return false;  // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
    print nextX,nextY
    return true
}
else if (arr[nextX,nextY] < value)
{
    if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
        return true
    return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
    if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
        return true
    reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}

Answer 4

Given a square matrix as follows:

[ a b c ]
[ d e f ]
[ i j k ]

We know that a < c, d < f, i < k. What we don't know is whether d < c or d > c, etc. We have guarantees only in 1-dimension.

Looking at the end elements (c,f,k), we can do a sort of filter: is N < c ? search() : next(). Thus, we have n iterations over the rows, with each row taking either O( log( n ) ) for binary search or O( 1 ) if filtered out.

Let me given an EXAMPLE where N = j,

1) Check row 1. j < c? (no, go next)

2) Check row 2. j < f? (yes, bin search gets nothing)

3) Check row 3. j < k? (yes, bin search finds it)

Try again with N = q,

1) Check row 1. q < c? (no, go next)

2) Check row 2. q < f? (no, go next)

3) Check row 3. q < k? (no, go next)

There is probably a better solution out there but this is easy to explain.. :)

Answer 5

Here's a simple approach:

1. Start at the bottom-left corner.
2. If the target is less than that value, it must be above us, so move up one.
3. Otherwise we know that the target can't be in that column, so move right one.
4. Goto 2.

For an NxM array, this runs in O(N+M). I think it would be difficult to do better. :)

Edit: Lots of good discussion. I was talking about the general case above; clearly, if N or M are small, you could use a binary search approach to do this in something approaching logarithmic time.

Answer 6

Interesting question. Consider this idea - create one boundary where all the numbers are greater than your target and another where all the numbers are less than your target. If anything is left in between the two, that's your target.

If I'm looking for 3 in your example, I read across the first row until I hit 4, then look for the smallest adjacent number (including diagonals) greater than 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Now I do the same for those numbers less than 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Now I ask, is anything inside the two boundaries? If yes, it must be 3. If no, then there is no 3. Sort of indirect since I don't actually find the number, I just deduce that it must be there. This has the added bonus of counting ALL the 3's.

I tried this on some examples and it seems to work OK.

Answer 7

Start in the middle. If this value is bigger than the target, then the target cannot be in the lower right quadrant. If it is smaller, then it cannot be in the upper left quadrant. You can thus do a binary search on the upper left to lower right diagonal, which will take O(log₂(max(n,m))). From the endpoint of this binary search, the target cannot be in the lower right nor the upper left "quadrant". You have now at least halved the problem space. Recurse on the remaining "quadrants". Overall time complexity seems to be O(log₂(max(n,m))^.log₂(n^.m)) = O(log₂(max(n,m)+n^.m)), which is asymptotically the same as O(log₂(n^.m)). If one of the dimensions gets much smaller than the other, this approaches the O(log₂n) of an ordinary binary search.

UPDATE: This is wrong. This algorithm is actually something like O(log₂(max(n,m))^.min(n,m)), as pointed out in the comments. Please redirect your attention to Jeffrey's and Nate's solutions. I am not sure about which is actually better now; I'll try to analyze. I am sorry for the confusion.

Answer 8

Well, to begin with, let us assume we are using a square.

1 2 3
2 3 4
3 4 5

1. Searching a square

I would use a binary search on the diagonal. The goal is the locate the smaller number that is not strictly lower than the target number.

Say I am looking for 4 for example, then I would end up locating 5 at (2,2).

Then, I am assured that if 4 is in the table, it is at a position either (x,2) or (2,x) with x in [0,2]. Well, that's just 2 binary searches.

The complexity is not daunting: O(log(N)) (3 binary searches on ranges of length N)

2. Searching a rectangle, naive approach

Of course, it gets a bit more complicated when N and M differ (with a rectangle), consider this degenerate case:

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17

And let's say I am looking for 9... The diagonal approach is still good, but the definition of diagonal changes. Here my diagonal is [1, (5 or 6), 17]. Let's say I picked up [1,5,17], then I know that if 9 is in the table it is either in the subpart:

            5  6  7  8
            6  7  8  9
10 11 12 13 14 15 16

This gives us 2 rectangles:

5 6 7 8    10 11 12 13 14 15 16
6 7 8 9

So we can recurse! probably beginning by the one with less elements (though in this case it kills us).

I should point that if one of the dimensions is less than 3, we cannot apply the diagonal methods and must use a binary search. Here it would mean:

• Apply binary search on 10 11 12 13 14 15 16, not found
• Apply binary search on 5 6 7 8, not found
• Apply binary search on 6 7 8 9, not found

It's tricky because to get good performance you might want to differentiate between several cases, depending on the general shape....

3. Searching a rectangle, brutal approach

It would be much easier if we dealt with a square... so let's just square things up.

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17
17 .  .  .  .  .  .  17
.                    .
.                    .
.                    .
17 .  .  .  .  .  .  17

We now have a square.

Of course, we will probably NOT actually create those rows, we could simply emulate them.

def get(x,y):
  if x < N and y < M: return table[x][y]
  else: return table[N-1][M-1]            # the max

so it behaves like a square without occupying more memory (at the cost of speed, probably, depending on cache... oh well :p)

Answer 9

This is a short proof of the lower bound on the problem.

You cannot do it better than linear time (in terms of array dimensions, not the number of elements). In the array below, each of the elements marked as * can be either 5 or 6 (independently of other ones). So if your target value is 6 (or 5) the algorithm needs to examine all of them.

1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10

Of course this expands to bigger arrays as well. This means that this answer is optimal.

Update: As pointed out by Jeffrey L Whitledge, it is only optimal as the asymptotic lower bound on running time vs input data size (treated as a single variable). Running time treated as two-variable function on both array dimensions can be improved.

Answer 10

EDIT:

I misunderstood the question. As the comments point out this only works in the more restricted case.

In a language like C that stores data in row-major order, simply treat it as a 1D array of size n * m and use a binary search.