findMedian Sample Code

Posted on Edited on In ,

Sample code of FindMedian Algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
chunkSize = 5

def findMedian(lst):
	if len(lst) == 0:
		return None
	if len(lst) % 2 == 0:
		num1 = findKth(lst, len(lst)//2)
		num2 = findKth(lst, len(lst)//2 - 1)
		num = (num1 + num2) * 1.0 / 2
	else:
		num = findKth(lst, len(lst)//2)

	print("result: " + str(num))
	return num

def findKth(lst, k):
	if len(lst) == 0:
		return None

	if len(lst) == 1:
		return lst[0]

	medians = []
	for i in range(0, len(lst), chunkSize):
		chunk = lst[i:min(i + chunkSize, len(lst))]
		chunk.sort()
		median = chunk[len(chunk)//2]
		medians.append(median)

	medianOfMedians = findKth(medians, len(medians)//2)
	# print("medianofmedians: " + str(medianOfMedians))

	high = []
	low = []
	same = []

	for num in lst:
		if num < medianOfMedians:
			low.append(num)
		elif num > medianOfMedians:
			high.append(num)
		else:
			same.append(num)

	if len(low) > k:
		return findKth(low, k)
	elif len(low) + len(same) > k:
		return medianOfMedians
	else:
		return findKth(high, k - len(low) - len(same))



assert findMedian([]) == None

assert findMedian([2]) == 2

assert findMedian([5,3]) == 4.0

assert findMedian([1,3]) == 2.0

assert findMedian([5,2,6]) == 5

assert findMedian([5,3,1]) == 3

assert findMedian([5,6,0,1]) == 3.0

assert findMedian([5,2,6,2,10,5]) == 5.0

assert findMedian([5,2,6,2,10,5,14]) == 5

assert findMedian([5,2,6,23,2,10,5,14]) == 5.5

assert findMedian([5,2,6,23,2,10,2, 5,14]) == 5

assert findMedian([5,2,6,23,2,10,2, 5,14, 5]) == 5.0

assert findMedian([5,2,6,23,2,10,2, 5,14, 12, 1349, 2, 349, 5, 10]) == 6