16

I had a following interview question.

There is an array of nxn elements. The array is partially sorted i.e the biggest element in row i is smaller than the smallest element in row i+1. How can you find a given element with complexity O(n)

Here is my take on this:

You should go to the row n/2.And start compare for example you search for 100 and the first number you see is 110 so you know it's either in this row or in rows above now you go n/4 and so on.

From the comments

Isn't it O(n * log n) in total? He has to parse through every row that he reaches per binary search, therefore the number of linear searches is multiplied with the number of rows he will have to scan in average. – Martin Matysiak 5 mins ago.

I am not sure that is a right solution. Does anyone have something better

Improve this question
6
  • 9
    Sounds correct to me. O(log n) to reduce to two candidate rows, O(n) to find the element in one of those rows. That's O(n) total. Commented Jun 4, 2011 at 9:28
  • You can't do better than binary search in a sorted array and you can't do better than a linear search in an unsorted one, so this seems optimal to me. Commented Jun 4, 2011 at 9:35
  • 1
    Is correct. Binary search, then linear search. You're not going to get better than O(n), because of the unsorted rows. Commented Jun 4, 2011 at 9:38
  • 1
    Isn't it O(n * log n) in total? He has to parse through every row that he reaches per binary search, therefore the number of linear searches is multiplied with the number of rows he will have to scan in average. Commented Jun 4, 2011 at 9:42
  • I think Martin is right does anyone have an idea to do it O(n)? Commented Jun 4, 2011 at 9:48

2 Answers 2

Reset to default
15

Your solution indeed takes O(n log n) assuming you're searching each row you parse. If you don't search each row, then you can't accurately perform the binary step.

O(n) solution:

Pick the n/2 row, instead of searching the entire row, we simply take the first element of the previous row, and the first element of the next row. O(1).
We know that all elements of the n/2 row must be between these selected values (this is the key observation). If our target value lies in the interval, then search all three rows (3*O(n) = O(n)).

If our value is outside this range, then continue in the binary search manner by selecting n/4 if our value was less than the range, and 3n/4 row if the value was greater, and again comparing against one element of adjacent rows.

Finding the right block of 3 rows will cost O(1) * O(log n), and finding the element will cost O(n).

In total O(log n) + O(n) = O(n).

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Actually by searching over the rows and comparing with the first (or any) value of a row) you limit the possible rows to 2 not 3.
@dcn, not true. { 1 2 3 ; 4 5 6 ; 8 7 9 } searching for any of {2,5,7} will yield that the target is indeed in the range [1,8] and yet to find the value I need to search all 3 rows, if I don't I'm not going to find one of the values.
No. Search for '2'. Compare to '5', which is bigger -> can only be in row 1&2. Same argument goes for searching 5 and 7.
My bad. I thought you were comparing with elements from consecutive rows, but reading it once more, prev and next are not supposed to be neighbors.
You could of course reduce it to 2 possible rows like this: via binsearch you find the smallest index of a row, maxrow , such that the first element of maxrow is bigger then the element you are looking for. Then only maxrow and maxrow-1 are candidates
|
3

Here is a simple implementation - since we need O(n) for finding an element within a row anyhow, I left out the bin-search...

void search(int n[][], int el) {
    int minrow = 0, maxrow;
    while (minrow < n.length && el >= n[minrow][0])
        ++minrow;
    minrow = Math.max(0, minrow - 1);
    maxrow = Math.min(n.length - 1, minrow + 1);
    for (int row = minrow; row <= maxrow; ++row) {
        for (int col = 0; col < n[row].length; ++col) {
            if (n[row][col] == el) {
                System.out.printf("found at %d,%d\n", row, col);
            }
        }
    }
}
Improve this answer

2 Comments

At first I was puzzled as to why you used a linear search through the rows, but then the penny dropped... O(n) + O(n) = O(log n) + O(n) = O(n), so why be fancy if you don't need to! :) (Of course if it was an m*n matrix then for optimality you'd need the binary search after all...)
@dcn - Can you please explain the logic behind the calculation of minrow and maxrow?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.