Поиск медианы несортированного массива без сортировки [дубликат] ⇐ C++

[Anonymous]

As shown in the title, given an unsorted array (arr) and it's size (size) I'm asked to find the median of it without sorting.

My thought:

If the length of the array is odd then It would be easy to find the median by iterating over every element and filter the other elements in the array to numbers less or greater than the candidate to be a median.

Problems I encountered:

If the length of the array is even, I thought about using a while loop that divides the size by 2 until size becomes an odd number and then use the code I wrote for odd arrays. The problem is I couldn't slice the array onto sub-arrays of the "new odd size".

Note: It's an intro to C++ course and we don't take complexity in mind as for now.

#include using namespace std; float median(int arr[] , int size) { float median1; if(size % 2 != 0) { for(int i=0; i < size; i++) { int less_than=0, greater_than=0; for(int j=0; j < size; j++) { if(arr < arr[j]) { greater_than += 1; } else if(arr > arr[j]) { less_than += 1; } } if (greater_than == smaller_than) { median1 = (float)arr } } } } Now I have to complete the code with for even-sized arrays. I'd like some direction for how can I slice the array (if possible) and I'm open to hear your ways on how can I solve this even without slicing.


Источник: https://stackoverflow.com/questions/781 ... ut-sorting