6

Possible Duplicate:
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?

The following was asked in a Google interview:

You are given a 2D array storing integers, sorted vertically and horizontally.

Write a method that takes as input an integer and outputs a bool saying whether or not the integer is in the array.

What is the best way to do this? And what is its time complexity?

Community
  • 1
  • 1
Josh Morrison
  • 7,488
  • 25
  • 67
  • 86

3 Answers3

19

Start at the Bottom-Left corner of the Matrix and follow the rules stated below to traverse the matrix:

The matrix traversal is based on these conditions:

  1. If the input number is greater than current number: Move Right
  2. If the input number is less than current number: Move Up.
  3. If the input number is equal to current number: Return Success
  4. If the input number is not equal to current number and no transition is possible: Return Fail

Time Complexity: (Thanks to Martinho Fernandes)

The time complexity is O(N+M). In the worst case, the element searched for is in the upper-left corner, meaning you'll go up N times, and left M times.

Example

Input matrix:

--------------
| 1 | 4 | 6  | 
--------------
| 2 | 5 | 9  |
--------------
| *3* | 8 | 10 |
--------------

Number to search: 4

Step 1: Start at the cell where you have 3 (Bottom-Left).

3 < 4: Move Right

| 1 | 4 | 6  | 
--------------
| 2 | 5 | 9  |
--------------
| 3 | *8* | 10 |
--------------

Step 2: 8 > 4: Move Up

| 1 | 4 | 6  | 
--------------
| 2 | *5* | 9  |
--------------
| 3 | 8 | 10 |
--------------

Step 3: 5 > 4: Move Up

| 1 | *4* | 6  | 
--------------
| 2 | 5 | 9  |
--------------
| 3 | 8 | 10 |
--------------

Step 4:

4=4: Return the index of the number

rkg
  • 5,559
  • 8
  • 37
  • 50
6

I would start by asking details about what it means to be "sorted vertically and horizontally"

If the matrix is sorted in a way that the last element of each row is less than the first element of the next row, you can run a binary search on the first column to find out in what row that number is, and then run another binary search on the row. This algorithm will take O(log C + log R) time, where C and R are, respectively the number of rows and columns. Using a property of the logarithm, one can write that as O(log(C*R)), which is the same as O(log N), if N is the number of elements in the array. This is almost the same as treating the array as 1D and running a binary search on it.

But the matrix could be sorted in a way that the last element of each row is not less than the first element of the next row:

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

In this case, you could run some sort of horizontal an vertical binary search simultaneously:

  1. Test the middle number of the first column. If it's less than the target, consider the lines above it. If it's greater, consider those below;
  2. Test the middle number of the first considered line. If it's less, consider the columns left of it. If it's greater, consider those to the right;
  3. Lathe, rinse, repeat until you find one, or you're left with no more elements to consider;

This method is also logarithmic on the number of elements.

R. Martinho Fernandes
  • 228,013
  • 71
  • 433
  • 510
  • 2
    And how can you find which row it's in? I don't think this will work, because there's no way of knowing if it's going to be in a row just by looking at the first column. You can know if it's definitely not going to be in a row, but that doesn't help much. – IVlad Mar 02 '11 at 01:42
0

The first method that comes to mind is a vertical binary search, followed by a horizontal one when you find the row it should be in. Complexity will be O(log NM) where N and M are the dimensions of the array.

Further explanation: Consider just the first number of every row. When you perform a binary search of these first numbers for the specified number, the result will be either the specified number if you're lucky, otherwise it will be the position before or after where the specified number would go depending on the binary search implementation. Once you find the two of the first numbers that the specified number should go between, you know that the number is in that row, and a second binary search will find the number if it is in the row.

user470379
  • 4,879
  • 16
  • 21
  • It could be in many rows. It's not necessary it **should** be in one row. – ypercubeᵀᴹ Mar 02 '11 at 01:40
  • The vertical binary search will give the row it should be in. – user470379 Mar 02 '11 at 01:41
  • How do you find the row it should be in by binary searching? You have no way to guarantee it's going to be in the row your search returns. – IVlad Mar 02 '11 at 01:46
  • @|\/|ad According to the question it is vertically sorted, meaning that every number above a certain number is less than or equal to that number and vice versa. Since we then know that every number above the position indicated by the binary search is less than the number and every number below the position indicated is greater, it must be in the same vertical position, AKA the same row. – user470379 Mar 02 '11 at 01:50
  • 2
    Consider the matrix with rows `1 2 3 | 3 4 100 | 4 5 1000`. We want to search for `100`. Your binary search will return the last row, and `100` isn't part of that last row. What next? – IVlad Mar 02 '11 at 01:51
  • @|\/|ad That's not vertically sorted unless you're being very generous with the definition of vertically. 100 is above 5, which breaks the vertical sort. If by vertical sort you mean each column is individually vertically sorted, with no guarantee on the array itself, that's a different question altogether. – user470379 Mar 02 '11 at 01:53
  • I am pretty sure the question means each row and column is individually sorted. – IVlad Mar 02 '11 at 01:56
  • @|\/|ad Based on the answers to the other question of which this is a duplicate, I would agree, but I would argue the text of the question should be changed. – user470379 Mar 02 '11 at 02:00