A nightly job logs one signed 32-bit integer per booking into a huge unsorted file. You need the median of all of them, but the file is far bigger than memory: you can read it from start to finish as many times as you want, but you can't load it, sort it, or keep a big chunk of it around.
Implement find_median(data) -> float.
data supports exactly two things:
len(data): the number of valuesn(n >= 1).for x in data: ...: one full sequential pass over the values, in the file's (unsorted) order. You may start as many passes as you like, up to 70.
Every value lies in [-2**31, 2**31 - 1]. The median is the middle value of the sorted data when n is odd, and the average of the two middle values when n is even. Return it as a float.
find_median(Dataset([7, -2, 9, 4, 4])) # 4.0 sorted: -2 4 [4] 7 9
find_median(Dataset([10, 1, 3, 8])) # 5.5 (3 + 8) / 2
find_median(Dataset([6])) # 6.0
(Dataset is the test's stand-in for the file: a thin wrapper around a list that you can only iterate.)
Requirements:
- O(1) extra memory: the tests measure your peak allocation, and building a list, sorting, or collecting a window of the data will fail.
- At most 70 passes over the data, and O(n) work per pass. The whole thing is O(32·n).
Show hint
Binary search on the value, not on positions. For a candidate m, one pass counts how many values are <= m. The k-th smallest value is the smallest m whose count reaches k. For even n you need the two middle order statistics; you can run the search twice, or find the lower one and get the upper with one more pass.