# Find median of an array

Programming

Share

In this programming tutorial we will find the median of an unsorted array.

### Problem statement

We are given an unsorted one dimensional array of size N consisting of numbers that can be negative, positive or zero. Find the median.

Input array 1:

``````[1, 3, 2, 0, 10, 7, 4, 8, 9, 6, 5]
``````

Input array 2:

``````[47, 32, 51, 19, 99, 38]
``````

### Solution

To find the median of the array we first sort the array in ascending order. Then we find the number of elements that is present in the array.

If the number of elements in the array is odd then the median is the middle element.

If the number of elements in the array is even then the median is the average of the two middle elements.

### Code

Python

``````def find_median(array):
size = len(array)
middle = int(size / 2)
if size % 2 == 0:
return (array[middle - 1] + array[middle]) / 2.0
else:
return array[middle]

input1 = [1, 3, 2, 0, 10, 7, 4, 8, 9, 6, 5]
input2 = [47, 32, 51, 19, 99, 38]

input1.sort()
input2.sort()
median1 = find_median(input1)
median2 = find_median(input2)

assert median1 == 5
assert median2 == 42.5

print('sorted', input1, 'median', median1)
print('sorted', input2, 'median', median2)
``````

### Output

``````sorted [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] median 5
sorted [19, 32, 38, 47, 51, 99] median 42.5
``````

#### Alternative

``````def find_median(array):
size = len(array)
middle = int(size / 2)
if size % 2 == 0:
return (array[middle - 1] + array[middle]) / 2.0
else:
return array[middle]

def partition(array, start, end):
pivot = array[start]
low = start + 1
high = end

while True:
while low <= high and array[high] >= pivot:
high = high - 1

while low <= high and array[low] <= pivot:
low = low + 1

if low <= high:
array[low], array[high] = array[high], array[low]
else:
break

array[start], array[high] = array[high], array[start]
return high

def quick_sort(array, start, end):
if start >= end:
return

pivot = partition(array, start, end)
quick_sort(array, start, pivot - 1)
quick_sort(array, pivot + 1, end)

input1 = [1, 3, 2, 0, 10, 7, 4, 8, 9, 6, 5]
input2 = [47, 32, 51, 19, 99, 38]

quick_sort(input1, 0, len(input1) - 1)
quick_sort(input2, 0, len(input2) - 1)

median1 = find_median(input1)
median2 = find_median(input2)

assert median1 == 5
assert median2 == 42.5

print('sorted', input1, 'median', median1)
print('sorted', input2, 'median', median2)
``````

### Time complexity

Time complexity for this is `O(nlogn)` as we are sorting.

Share