median search Algorithm

The median search algorithm is a selection algorithm that aims to find the median value in an unsorted list of numbers. The median is the value that separates a list into two equal halves, with one half containing all the values smaller than the median, and the other half containing all the values larger than the median. This algorithm is particularly useful in a wide range of applications such as statistical analysis, data mining, and computer vision, where determining the central tendency or midpoint of the data is important for making accurate predictions and decisions. The median search algorithm works by employing a divide-and-conquer strategy, which involves recursively partitioning the input list into smaller sublists until the median is found. The first step involves selecting a pivot element from the list, which can be any element in the list, although choosing a value closer to the actual median will result in faster execution. Then, the algorithm rearranges the list elements such that all the values less than the pivot are placed before it, and all the values greater than the pivot are placed after it. This process is known as partitioning, and it effectively places the pivot in its final sorted position. Next, the algorithm compares the position of the pivot with the target median position, and if it matches, the pivot is returned as the median. If the pivot's position is less than the median position, the algorithm continues its search on the right sublist, and if it's greater, it searches the left sublist. This process is repeated until the median is found, resulting in an efficient and effective solution with an average time complexity of O(n), where n is the number of elements in the list.
#include<iostream>
#include<math.h>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
vector<int>v;
vector<int>s1;
vector<int>s2;
vector<int>s3;
template <class X>
void comp(X x)
{
    if(s1.size()>=x && s1.size()+s2.size()<x)
    {
        cout<<s2[0]<<" is the "<<x+1<<"th element from front";
    }
    else if(s1.size()>x)
    {
        sort(s1.begin(),s1.end());
        cout<<s1[x]<<" is the "<<x+1<<"th element from front";
    }
    else if(s1.size()+s2.size()<=x && s3.size()>x)
    {
        sort(s3.begin(),s3.end());
        cout<<s3[x-s1.size()-s2.size()]<<" is the "<<x+1<<"th element from front";
    }
    else
    {
        cout<<x+1<<" is invalid location";
    }
}
int main()
{
    for(int i=0;i<1000;i++)
    {
        v.push_back(rand()%1000);
    }
    for(int r:v)
    {
        cout<<r<<" ";
    }
    int median=rand()%1000;
    cout<<"\nmedian="<<median<<endl;
    int avg1,avg2,avg3,sum1=0,sum2=0,sum3=0;
    for(int i=0;i<1000;i++)
    {
        if(v.back()==v[median])
        {
            avg1=sum1+v.back();
            s2.push_back(v.back());
        }
        else if(v.back()<v[median])
        {
            avg2=sum2+v.back();
            s1.push_back(v.back());
        }
        else
        {
            avg3=sum3+v.back();
            s3.push_back(v.back());
        }
        v.pop_back();
    }
    int x;
    cout<<"enter the no. to be searched form begining:- ";
    cin>>x;
    comp(x-1);
    return 0;
}

LANGUAGE:

DARK MODE: