Tired of TWO HEAP/SET solutions? See this segment dividing solution (c++)
\n    class MedianFinder {    \n    \n    / The idea of dividing existing numbers into several ranges:\n    \n       Say we already have 10k numbers in vector, 
\n    class MedianFinder {    \n    \n    /* The idea of dividing existing numbers into several ranges:\n    \n       Say we already have 10k numbers in vector, \n       each time adding a number requires sorting all 10k numbers, which is slow.\n    \n       To optimize, we can store 10k numbers in several (say 10) vectors, \n       and nums in each vector are sorted.\n       \n       Then each time we add a number, just need to find one vector with correct range,\n       insert the number and sort this vector only. Since its size is relatively small, it's fast.\n       \n       When we have a vector's size greater than a threshold, just split it into two halfs.\n       \n    */\n    \n    public:\n        vector<vector<int>*> raid; // store all ranges\n        int total_size;\n\n        MedianFinder() {\n            total_size=0;\n            raid.push_back(new vector<int> ());\n        }\n        \n        void addNum(int num) {\n            vector<int>* correctRange=NULL;\n            int targetIndex;\n            \n            // find the correct range to insert given num\n            for (int i=0; i<raid.size(); i++)\n                if ( raid.size()==1 ||\n                     (i==0 && num<=raid[i]->back()) || \n                     (i==raid.size()-1 && num>=raid[i]->at(0)) ||\n                     (raid[i]->at(0)<=num && num<=raid[i]->back()) ||\n                     (num > raid[i]->back() && num < raid[i+1]->front()) )\n                {\n                    correctRange = raid[i];\n                    targetIndex = i;\n                    break;\n                }\n            \n            // put num at back of correct range, and sort it to keep increasing sequence\n            total_size++;\n            correctRange->push_back(num);\n            sort(correctRange->begin(), correctRange->end());\n                    \n            // if current range's size > threshold, split it into two halfs and add them back to this.raid\n            const int max_size = 30;\n            int len = correctRange->size();\n            if (len > max_size) {\n                vector<int> *half1 = new vector<int>(correctRange->begin(), correctRange->begin()+len/2);\n                vector<int> *half2 = new vector<int>(correctRange->begin()+len/2, correctRange->end());\n                \n                delete correctRange;\n                raid[targetIndex]=half2;\n                raid.insert(raid.begin() + targetIndex, half1);\n            }\n            \n        }\n    \n        // iterate thru all ranges in this.raid to find median value\n        double findMedian() {\n            if (total_size==0)\n                return 0;\n            \n            int mid1 = total_size/2;\n            int mid2 = mid1 + 1;\n            \n            int leftCount=0;\n            double first, second;\n            for (auto r : raid) {\n                if (leftCount<mid1 && mid1<=leftCount+r->size())\n                    first = r->at(mid1 - leftCount - 1);\n                    \n                if (leftCount<mid2 && mid2<=leftCount+r->size()) {\n                    second = r->at(mid2 - leftCount - 1);\n                    break;\n                }\n                leftCount += r->size();\n            }\n            \n            if (total_size % 2)\n                return second;\n            else\n                return (first + second)/2;\n        }\n    };
[]