Median Search
123456789101112131415161718192021222324252627282930313233343536373839404142434445
// Ichlalsul Bulqiah
// 190535646047
#include <iostream>
using namespace std;
int medianSearch(int arr[], int length, int topIdx, int bottomIdx = 0) {
int k = ((length%2 == 0) ? length/2 : (length/2) + 1);
int s = bottomIdx+1;
int pivot = arr[bottomIdx];
for (int i = bottomIdx+1; i<=topIdx; i++) {
if (arr[i] <= pivot) {
s++;
for (int j=bottomIdx; j<i; j++) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
tmp = arr[i];
}
}
}
if (s == k) {
return arr[s-1];
}
else if (s < k) {
return medianSearch(arr, length, topIdx, s);
}
else if (s > k) {
return medianSearch(arr, length, s, bottomIdx);
}
}
int main() {
int arr[] = {3, 7, 2, 8, 6};
int foo =medianSearch(arr, 5, 4);
cout << foo << endl;
return 0;
}
Cpp
INFO