bunny9's blog

Stuck with one binary search problem.
By bunny9, history, 5 years ago, In English

Hi,

I'm trying to solve matrix median problem from interviewbit.com.

Can anyone point me in right direction?

Given a N cross M matrix in which each row is sorted, find the overall median of the matrix. Assume N*M is odd.

For example,

Matrix=
[1, 3, 5]
[2, 6, 9]
[3, 6, 9]

A = [1, 2, 3, 3, 5, 6, 6, 9, 9]

Median is 5. So, we return 5.
  • Vote: I like it
  • -13
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you directly search for the result value. To check if a value $$$x$$$ is bigger than the median you just need to count the amount of values smaller than $$$x$$$ (if this is more than $$$n \cdot m/2$$$, $$$x$$$ is bigger than the median). To calculate this you can search in all $$$n$$$ rows the position of $$$x$$$ and calculate the sum over those positions.

→ Reply
»
5 years ago, # |
← Rev. 13   Vote: I like it 0 Vote: I do not like it

We can formulate the problem as finding the smallest number (X) such that the count of numbers >= X is > $$$(N * M) / 2$$$

Since this function is monotonic we can binary search for X. To find the answer for a particular X, we use another binary search over each row (std : upper_bound / lower_bound would be good) to find count of numbers >= X for that row and sum this count up for each row.

Based on this sum we can decide how to move the lo and hi pointers of our outer binary search.

→ Reply