An interview question from Google [duplicate]

This question already has answers here: Closed 11 years ago.

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?

---

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

---

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.

---

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.