Timeline for Finding median of 2 sorted arrays in O(log n)
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2017 at 18:10 | history | tweeted | twitter.com/StackCompSci/status/828667096464838658 | ||
| Feb 6, 2017 at 1:59 | comment | added | Evil | @Paparazzi when arrays do not even overlap it is a trivial case when after determining in which order these are ($AB$ or $BA$) the only needed action is to take index and return the mean. It may be like this $A=[1,2,3], B=[4,5,6]$ so it is $AB$ and the median is $\frac{3+4}{2} = 3.5$. Frankly speaking I rarely use that definition of median, I stick to taking one of them (smaller in my case) when the array is of even length, saves all this effort and the median is always a sample from my data (so here I would say it is 3, not 3.5). | |
| Feb 6, 2017 at 0:29 | vote | accept | New_Coder | ||
| Feb 5, 2017 at 18:55 | answer | added | Evil | timeline score: 4 | |
| Feb 5, 2017 at 14:46 | comment | added | paparazzo | Could have two arrays that do not even overlap. I doubt you can guarantee O(log n). | |
| Feb 5, 2017 at 13:54 | comment | added | New_Coder | @Evil Do you think, the median of both the arrays will be the average of medians of A and B. In above example, medians of A and B are 8 and 5. Its average is (8+5)/2=6.5, but the median should be 7. So, median will be celling of 6.5 that is 7. Is that correct? | |
| Feb 5, 2017 at 4:43 | comment | added | New_Coder | List all the elements in both the arrays between 5 and 8 is 6, 7, 8 and 7 is the median of both the arrays. Does that mean median will be the middle element of all the elements between the range (median of A and B)? | |
| Feb 5, 2017 at 4:27 | comment | added | Evil | The median of $B$ is $5$, since you take $\frac{a+b}{2}$, so your median is between 5 and 8, so far so good. How can you use the new obtained info that median is in this range? | |
| Feb 5, 2017 at 4:20 | comment | added | New_Coder | @Evil Thanks for answering. In the above example median of A is 8 and B is 10 [(3+7)/2]. 8 is not present in B and 10 is present in A. However, actual median is 7, which is not even between 8 and 10. Please help! | |
| Feb 5, 2017 at 3:58 | comment | added | Evil | You cannot sort $n$ numbers in time less than $n$. Try another approach that does not require sorting. Start from finding median of the both arrays and finding them in the opposite arrays (median of $A$ in the array $B$ and the median of $B$ in the array $A$). Think what would be the next step. | |
| Feb 5, 2017 at 3:28 | history | asked | New_Coder | CC BY-SA 3.0 |