Leetcode #4. Median of Two Sorted Arrays

[arctic garnet]

https://leetcode.com/problems/median-of-two-sorted-arrays/

My solution:

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int size = nums1Size + nums2Size;
    int odd = !(size%2);
    int i = 0, i1 = 0, i2 = 0;
    bool t = false;
    int r[2] = {0,0};
    while(i < size/2+1){
        if(i1 >= nums1Size || (i2 < nums2Size && nums1[i1] > nums2[i2])){
            r[t] = nums2[i2];
            i2++;
        }else{
            r[t] = nums1[i1];
            i1++;
        }
        t = odd ? !t : false;
        i++;
    }

    return odd ? (double)(r[0]+r[1])/2 : r[0];
}

Looking for feedback again. The task says to make the complexity O(log (m+n)) but that sort of feels impossible. Just the act of merging the arrays needs to be worse than O(log (m+n)) right? Ending up O((n+m) log (m+n))?

I guess in other languages where they don't think about the merging steps they might see it as log (m+n) just for the searching for median in one merged sorted array?

Or maybe my understanding of O notation is even worse than I feel it already is.

[sterile abyss]

If you do merge, it's wrong absolutely.

O(log) complexity requires you to do something even like guess but amazingly hit the correct answer.

[kind flax]

O(log) complexity screams of binary search. finding the median of a single sorted array is O(1). so i would assume that the solution consists of searching for the median of one array within the other and progressing somehow from there

[wispy ledge]

no, I think the complexity stated is possible

[wispy ledge]

merging the arrays is the naive solution which is obvious

I might be wrong about this, but I think the median of two sets falls between the medians of each set

this is actually not an easy problem at all

[arctic garnet]

@wispy ledge, Got me wondering if you thought of another way 😮 Going to start another leetcode problem now if not.

[wispy ledge]

I haven't solved it in the alotted time complexity yet, no

[arctic garnet]

Also, would mine be O((n+m)/2) ?

I'm not used to O notation.

[wispy ledge]

O(n+m) yes

[wispy ledge]

I haven't really thought this through fully yet, but median is defined as the element that is smaller/greater than exactly half the elements

according to that definition you can use a binary search algorithm to find that number

by utilizing both sorted arrays to somehow keep track of how many numbers your guess is smaller/greater than

and if it reaches n, n, you return it or alternatively if it's n, n+1 for the odd case, you return the mean of two such numbers

I'll give it a try over this weekend probably, sounds interesting

[arctic garnet]

I did learn about binary search today after it was mentioned here. As far as I can see you need to be able to find the middle value.

In the case:
{1,3,6,200} {-10,201,203,204,205,206}

The answer is 200.5

I can't see how a binary search would work when you can't tell where the center should be, without doing the equality checks part of the merge.
It doesn't seem possible (From the perspective of someone that just read what binary search is a few minutes ago and could be very very wrong)

[wispy ledge]

binary search typically searches in a given sorted array

not over two sorted arrays

but, just as intuition... imagine taking the median from the first array and searching for it in the second array

it immediately rules out almost all the options

like... if we look at the edge cases

I need to think about this

but you can keep track of how many values overall the thing you're searching is greater than or smaller then

and your goal is to reach exactly (size1 + size2) / 2

[arctic garnet]

The only way to know if you've reached that point is by comparing the arrays to a point.

That first half could be in any order

which is what makes me wonder what a binary search would do different to just checking the difference on every value up to half way.

[wispy ledge]

the first half?

[arctic garnet]

First half of what the merged array would be.

[wispy ledge]

but you're not merging the array

I am not sure I follow

merging the array already costs you O(n+m)

so you've failed at that point

[arctic garnet]

{1} {-5,-4,-3,3,4,5,6,7,8,9,10,1100}
My point being it shouldn't be possible to use binary search without it being somewhat sorted.

[wispy ledge]

what is that thing that you think you're doing the binary search on?

both of these arrays are sorted

in this example, you can take the median of the larger array and search for it in the other array

by knowing what index you land on, you know how many values that median is greater than or smaller than in the merged array

and that gives you an anchor point to search for more

this is a hand wavy explanation obviously

so e.g., the median of the larger array here is 5.5, and if you search for 5.5 in the smaller array you'll reach the conclusion that it's larger than all the numbers in the smaller array

in this case it'll be larger than 6 + 1 numbers, but you want it to be larger than 6.5 numbers

or put it differently, you want to find the number that is larger than 7 numbers and the number that is larger than 6

I really just need to do a few cases by hand to get an intuition for this

[arctic garnet]

Hm. So if I'm understanding right:

a{20,40,60,80,100} b{10,30,50,70,90,110,130,150}

first search would be `b[4.5] = 80`, a[3] = 80.

a key is 3, b key is 4.5?
len is 13

3+4.5 = 7.5? sorta tells you your number is too low? Or does <len/2 mean your answer was too high?

Answer being 70. No idea how to get there.

I'm lost as to what the next search would be.

Yeah after thinking it out

It's the 2nd step

I just don't get what you would do next

[wispy ledge]

the idea in binary search is to always narrow down the options

[arctic garnet]

I understand it narrows down possiblities. But what do you try next there?

[wispy ledge]

actually here's another way to look at it

you start with the median from b which is 80 and we know that is between index 4 and 5 of b, right?

so now, you search for that median in the other array, which you actually find in index 3 of a

since 8 is greater than 7 numbers out of 13, you know it's a higher than the actual median

so go down a number in a, which gives you 60 and search for that in b

[arctic garnet]

How do you get 8? Why the round up?

[wispy ledge]

okay again

a{20,40,60,80,100} b{10,30,50,70,90,110,130,150}

you start with 80 from b which you know is greater than 4 numbers in b

you search for it in a, which tells you it's greater than 3 numbers in a

so overall it's greater than 7 numbers out of 13

right?

[arctic garnet]

Yes. 7.5 so .5 more.

[wispy ledge]

no, forget about the index

I am talking about the merged array

you know right away that 80 is greater than 4 numbers in b and by doing a binary search on a, you also know it's greater tahn 3 numbers in a

in both of these arrays you have 13 numbers

so it's 7 out of 13 which is more than half of the numbers

[arctic garnet]

I see how we know it's greater than 7 numbers. What's the next step?

[wispy ledge]

okay

now this step I need to think about, but basically with this information you can look for the smaller next number in a, which is 60

and search for that in b

which will tell you it's greater than 3 numbers in b and you already know it's greater than 2 numbers in a

so this is 5 out of 13

[arctic garnet]

At which point we've already done more equality checks than just half merging the two arrays no?

[wispy ledge]

no!

it's binary search

[arctic garnet]

Maybe the bit I rea don binary search wasn't in depth enough. But I thought it was just guessing center, equality check, guess lower or higher and repeat based ont hat

[wispy ledge]

merging the arrays means going over all the items in both arrays

you don't actually need to go over all the items in the range you're searching

that's the whole point of binary serach

anyway, 60 is greater than 5 overall and 80 greater than 7

so you need something between 60 and 80

which again, you search for in b

(you don't need to search the whole array of b because you've already narrowed it down before... always keep your anchors)

what do you find? 70

like I said, I don't know the exact details of this algorithm, but it seems to be a back and forth binary search between the two arrays

[arctic garnet]

I'm missing steps here. What are you doing with the anchors to find 70?

[wispy ledge]

let's do this more formally now

a{20,40,60,80,100} b{10,30,50,70,90,110,130,150}

[arctic garnet]

Our prev search tells us it's lower than id 4.5 in b or lower than 3 in a

Right?

Was anythign else learnt from the first search?

I wanna make sure I'm not missing shit here.

[wispy ledge]

you keep anchors for b and a in the beginning

since you start with b first, you can say the anchors for be are 0 and 4

for a it's 0 and 4 (coincidentally, unrelated to the b... in the beginning you simply have the whole thing)

actually know what, no... you start with the anchors for b being 0 and 7

[arctic garnet]

Ah. So the first search told us it's within 0-4 in b and hasn't given any info on a. Correct?

[wispy ledge]

yeah

I mean

you take b's median

this is 80

you search for that in a, that narrows it down to 0-3 in a

yeah it's all about narrowing down these anchors

but you see how this doesn't require merging the arrays?

I need to concretely implement this to fully grasp how to do it