فکر نکنم از هر روشی که قرار باشه انجام بدید باید مرتب سازی صورت بگیره در ضمن خود stl هم تابعی برای اینکار داره که خودش هم به صورت ناحیه ای همان ناحیه ای که شما از طریق پارامتر براش مشخص می کنید داده ها را در ابتدا مرتب می کنه.
std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
std::cout << "The median is " << v[v.size()/2] << '\n';