Error: Find Medium Number from 2 Sets

[waranthem]

#include <iostream>
#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int getMedium (set <int>, set <int>);

int main ()
{
  set<int> myset1;
  set<int> myset2;
  set<int>::iterator it;

  for (int i=1; i<=10; ++i) myset1.insert(i*10);    // set: 10 20 30 40 50 60 70 80 90 100

  cout << "myset1 contains:";
  for (it = myset1.begin(); it!=myset1.end(); ++it)
    cout << ' ' << *it;

  cout << '\n';

  int myints[]= {5,10,15,20,25,30,35,40,45,50,55};

  myset2.insert(myints,myints+11);

  cout << "myset2 contains:";
  for (it=myset2.begin(); it!=myset2.end(); ++it)
    cout << ' ' << *it;

  cout << '\n';

  getMedium (myset1, myset2);

  cout << '\n';

  return 0;
}

int getMedium (set <int> myset1, set <int> myset2)
{
    int setsize = myset1. size () + myset2. size ();
    setsize = setsize / 2;

    set<int>::iterator it1;
    set<int>:: iterator it2;

    for (int i = 0; i < setsize; i++)
    {
        if (*it1 > *it2)
        {
            it1++;
        }
        else
        {
            it2++;
        }
    }
}

I know an approach with better time complexity would be to utilize something such as advance iterator. Trying another approach with a time complexity of something like n1+n2. Currently getting a 'segmentation fault: 11' error. How would I go about finding a median value from two sets using brute force?

[lastchance]

Your iterators haven't been initialised in getMedium() - they should start by pointing to myset1.begin() and myset2.begin().

You neither calculate, set or return anything in routine getMedium().

The correct term is median. For an even number of elements it will be the average of the middle two.

[waranthem]

Oops, appreciate the help lastchance. My tired eyeballs overlooked that. I think I miscommunicated in the title and content. How would I go about finding a median value from two sets using brute force?

[keskiverto]

Even if initialized:
set1 {42}
set2 {7, 9, 11, 12, 13]
it1 points to 42, it2 points to 7
(setsize=(1+5)/2=3)

Lets loop:
*it1 > *it2 means 42 > 7
true => it1++
it1 now points to set1.end()

Next iteration:
*it1 > *it2 means *(set1.end()) > 7
=> crash and burn


Start with simpler logic:
set3 = set1 + set2
get median of set3

However, if
set1 {2, 7}
set2 {2, 42}
=>
set3 would become {2, 7, 42} and median 7
multiset3 would become {2, 2, 7, 42} and median 4.5

In other words, how do you want to do it?

[waranthem]

Um, I want to do it so that it finds the median according to the set size. Haven't accounted for even set size tho.

Like if the set size for both set 1 and set 2 is 21 , the median value should be in the 11th one.

In myset1, the values are ... 10, 20, 30, 40, 50, 60, 70, 80, 90, 100.
In myset2, the values are ...5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55.

Ideally, the median value should be 40.

int getMedium (set <int> myset1, set <int> myset2)
{
    int setsize = myset1. size () + myset2. size ();
    setsize = setsize / 2;

    set<int>::iterator it1 = myset1. begin ();
    set<int>:: iterator it2 = myset2. begin ();
    set<int>:: iterator it3;

    while ( (it1 != myset1. end ()) && it2 != myset2. end () )
    {
        if (*it1 > *it2)
        {
            it1++;
        }
        else
        {
            it2++;
        }
        it3++;
    }
    cout << "Median Value is " << *it3;
}

Here is what I got so far with a different approach. It is displaying 50. Still pretty confused as well.

[lastchance]

I think you would make life easier if you put them in a single container first, then moved to the appropriate position in that container. The container would be a multiset<int> if you allowed duplicates and a set<int> if you didn't.

[keskiverto]

Your it3 is uninitialized.

If you don't want to use single container, then consider the logic of std::merge
http://www.cplusplus.com/reference/algorithm/merge/

Adapted to your problem the logic could be something like:

size_t count = 0;
const size_t Size = ( set1.size() + set2.size() )/2;
int medi {};
while (true) {
  if (first1==last1) { medi = foo( first2, last2, count, Size ); break; }
  if (first2==last2) { medi = foo( first1, last1, count, Size ); break; }
  if ( *first2 < *first1 ) {
    if ( Size == count ) { medi = *first2; break; }
    ++first2;
  } else {
    if ( Size == count ) { medi = *first1; break; }
    ++first1;
  }
  ++count;
}

(Totally unchecked code, and does not handle median of even set size.)

[lastchance]

Note that it returns a double and I've changed the name.

double getMedian( set<int> myset1, set<int> myset2 )
{
        set<int> myset( myset1.begin(), myset1.end() );    // Choose this for no duplicates
// multiset<int> myset( myset1.begin(), myset1.end() );    // Choose this to allow duplicates

   myset.insert( myset2.begin(), myset2.end() );   
                                                    
   cout << "Combined set contains:";
   for ( auto it = myset.begin(); it != myset.end(); ++it ) cout << ' ' << *it;
   cout << '\n';                                           

   size_t size = myset.size();                             // To do: check size isn't 0
   int target = ( size - 1 ) / 2;                          // Integer division gives correct "index" if odd, lower "index" if even
   auto it = myset.begin();
   for ( int i = 0; i < target; i++ ) it++;                // Advance by target positions, taking you to "index" target
   double result = *it;
   if ( size % 2 == 0 )                                    // Even case
   {
      it++;
      result = 0.5 * ( result + *it );                     // Average with next
   }
   
   return result;
}

myset1 contains: 10 20 30 40 50 60 70 80 90
myset2 contains: 5 10 15 20 25 30 35 40 45 50 55
Combined set contains: 5 10 15 20 25 30 35 40 45 50 55 60 70 80 90
Median is 40