I'm looking for a hint to help me think through/solve the problem of finding the median of two sorted lists/arrays in O(log(m+n)) time, where m,n are the sizes/lengths of each list, respectively.
I can immediately think of an obvious O(m+n) time algorithm using big-theta of m+n space, as follows: Merge the two lists into a new list in O(m+n) time. Find the middle element of that list in O(1) time (more particularly, if the merged list is even in length, take the mean of the floor of the element at index (m+n)/2, and the ceiling of the element at index (m+n)/2, otherwise the merged list length is odd and just use the element at (m+n)/2... potentially update logic for off-by-one depending on zero- or one-indexing).
But I don't immediately see how the median could be found in logarithmic time. Any hints would be appreciated!