We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Find the Median
  5. Discussions

Find the Median

Sort by

recency

|

553 Discussions

|

  • vtu24374
     + 0 comments

    include

    include

    using namespace std;

    int findMedian(int arr[], int n) { sort(arr, arr + n); return arr[n / 2]; }

    int main() { int n; cin >> n; int arr[n]; for (int i = 0; i < n; i++) { cin >> arr[i]; }

    cout << findMedian(arr, n) << endl;

return 0;

    }

  • david1194
     + 0 comments

    Sort, then pick the midpoint seemed the easiest. But sort is O(n log n), right? If so, can we use a better sort and get to O(n)? So,if we look at a sorted array and median is midpoint, then we can assume the NthSmallest integer where n is the midpoint is what we are looking for. Then we only have to adjust our sort until then.

    Typescript:

    function findNthSmallest(arr: number[], n: number): number {
    let left: number = 0;
    let right: number = arr.length - 1;
    
    while (left <= right) {
        const pivotNdx = partition(arr, left, right);
        
        if (pivotNdx === n) {
            return arr[pivotNdx];
        // we know what's left of index is lower than everything else
        } else if (pivotNdx < n) {
            left = pivotNdx + 1;
        // we know what's right of index is larger than everything else
        } else {
            right = pivotNdx - 1;
        }
    }
}

function partition(arr: number[], left: number, right: number): number {
    const pivot = arr[right];
    let i = left - 1;
    
    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
}

function findMedian(arr: number[]): number {
    // find mid smallest number, use own copy of arr
    return findNthSmallest([...arr], Math.floor(arr.length / 2));
}

  • adadasaivenkat01
     + 0 comments
    def findMedian(a):
 # Write your code here
    m=0
    a.sort()
    f=[]
    l=[]
    le=len(a)
    if le%2!=0:
        m=le//2
        return a[m]
    elif le%2==0:
        t=le//2
        f=a[:t]
        l=a[t:]
        return (f[-1]+l[0])/2

  • todorov_stanimir
     + 0 comments

    JavaScript:

    function findMedian(arr) {
  return [...arr].sort((a, b) => a - b)[Math.floor(arr.length / 2)];
}

  • dorirgob
     + 0 comments

    Java:

    public static int findMedian(List<Integer> arr) {
	Collections.sort(arr);
	return arr.get((arr.size() - 1) / 2);
}