0

Hi i was asked in an interview about this question. I did google a lot after the interview but still i can't get the clear solution. Can somebody tell me how i can return the (row,col) pairs (yes! return two values) using the function signature he mentioned.

void find(int A[][10], int m, int n, int target, int& row, int& col)
orlp
  • 112,504
  • 36
  • 218
  • 315
night_hawk
  • 101
  • 1
  • 6
  • Are you sure the col is not also a reference? How is the array sorted? – Ivaylo Strandjev Apr 03 '12 at 08:39
  • 1
    @aleroot yeah sure reference to row in plain c... – Ivaylo Strandjev Apr 03 '12 at 08:41
  • 1
    The problem is not explained clearly enough - what are `n` and `m`? Why are you returning two values? What do you mean by a "2D sorted array?" I would guess the array is `nxm` in size, and "Sorted 2D array" means a 2D array where the rows and columns are each sorted individually, but in that case there is only one return value, and no `O(log m + log n)` solution *(you can however do it in `O(n+m)` by simply traversing the opposite diagonal)*. Or is this a different problem? – BlueRaja - Danny Pflughoeft Apr 03 '12 at 08:42
  • 1
    @BlueRaja: "I would guess the array is nxm in size" - which raises the question of why an `int(*)[10]` is passed as parameter, rather than either an `int**` to be addressed as `A[i][j]` or an `int*` to be addressed as `A[i*m + j]`. – Steve Jessop Apr 03 '12 at 08:45
  • My guess is the array is sorted in a manner that each consecutive row is not less then all the previous rows. In this case what we would have is simply a sorted array of size N*m placed in several rows and then the solution would be O(log(n*m)) = O(log(n) + log(m)). – Ivaylo Strandjev Apr 03 '12 at 08:49
  • Possible duplicates: [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?](http://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom) and [find an element in a sorted matrix](http://stackoverflow.com/questions/6603070/find-an-element-in-a-sorted-matrix) – Paul R Apr 03 '12 at 08:50
  • This is a clumsy way to ask a question. If you didn't understand the question, you should have asked the interviewer to clarify. – kasavbere Apr 03 '12 at 17:39

2 Answers2

2

I'm guessing that the matrix is sorted in this way:

1 2 3
4 5 6
7 8 9

Apply binary searching twice, for example to find element 5:

  • Find the row where first col<=5 and second col>=5
  • In that row, find the element 5

Binary search is just the method of picking the element in the middle. If it's too large, pick the first half, otherwise pick the second half. Repeat until you find the element you're looking for.

Emil Vikström
  • 90,431
  • 16
  • 141
  • 175
  • but this is not the complexity he's looking for. – Karoly Horvath Apr 03 '12 at 08:59
  • 1
    Karoly, I'm pretty sure it is. Can you elaborate on your dismissal? I'm more than happy to learn something new here! – Emil Vikström Apr 03 '12 at 09:06
  • ahh I see you picked a fully sorted matrix.. in that's case yes, that's like searching in an M*N array, which is log(M*N) = logM + logN. question is what he meant by 2d sorted array.. (note: for exactly this reason I voted to close as he still haven't answered a question). – Karoly Horvath Apr 03 '12 at 09:10
  • Yes, I made that assumption. I just realized that my solution is suboptimal in that case as well, since you 8as you say) can treat it like one large array instead of like a matrix. The complexity shouldn't change, though. – Emil Vikström Apr 03 '12 at 09:16
2

Your question title differs from what the actual question is.so not sure whether u want a searching method or how to return values from that function signature. So not sure exactly what u need and whether the detail below is correct or not. as the two variables row and col are references.justdo a search and populate the values inside the function.then you can use those two references in the place where you call. for eg: if you call the function as below from anywhere else:

find( dptr, 5,  19, 5, i,j);

i and j will be populated inside the function.and you can use them after the call.this implies the two values are returned from the function.

Vijay
  • 65,327
  • 90
  • 227
  • 319