Home Arrays Find the median of a sequence of n integers.

Find the median of a sequence of n integers.

by nikoo28
0 comment

Question: Given a sequence of integers, find the median of the integers?

Input: arr [] = {15, 23, 4, 16, 8, 42}. Find median.
Output: 15

Since the question does not specify anything we cannot assume that the given array is a sorted one. The definition of median is the (n/2)th element of a sorted sequence of integers.
This definition makes our approach simpler. All we need to do is sort the integers and then return the (n/2)th element.
Here is the code for above approach. I use quick sort to sort the array.


void swap(int *i, int *j) {
	int temp = *i;
	*i = *j;
	*j = temp;

int partition(int arr[], int start, int end) {
	int pivot = arr[end];
	int i = start, j = end-1;
	while(i<=j) {
		while(arr[i]<pivot)    i++;
		while(arr[j]>pivot)    j--;
		if(i<=j) {
	return i;

void performQuickSort(int arr[], int start, int end) {
	if(start<end) {
		int p = partition(arr, start, end);
		performQuickSort(arr, start, p-1);
		performQuickSort(arr, p+1, end);

void quickSort(int arr[], int size) {
	performQuickSort(arr, 0, size-1);

// driver program to find median
int main(void)
	int i;
	int arr[6] = {15, 23, 4, 16, 8, 42};
	int size = 6;


	printf("Median:- %d",arr[size/2]);

	return 0;

Time Complexity:- O (n*log (n)) due to quick sort.

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More