Median Search

// 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;
}