unemployed's blog

Find Median in 2-d sorted array(sorted in both order column and row wise)?
By unemployed, 12 years ago, In English

Given 2 dimensional sorted array(Both row and column wise sorted) write a efficient algo to find median.

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

Looks very similar to finding k-th element of two sorted arrays, which I've seen at TC forums.

Use binary search over the value of the median. Complexity would be O(Rlog(C) log(MaxVal)).

Guess it can be done in a better way since this way you wouldn't use the fact that the columns are sorted.

→ Reply