Поиск медианы в большом файле целых чисел

Question

Меня спросили в интервью следующее.Я не получил это, но пытался решить это дома.Я считаю, что мы должны использовать алгоритм Медиана медианы ...

Q: Поиск медианы в большом целом файле Файл целых чисел

Найти медиану из большого файла целых чисел.Вы не можете получить доступ к номерам по индексу, можете получить доступ к нему только последовательно.И числа не могут поместиться в памяти.

Я нашел решение онлайн (переписано на Python), но есть несколько вещей, которые я не понимаю .. Я вроде получаю алгоритм, но не уверен на 100%.

а) Почему мы проверяем left >= right?

б) Когда count < k, мы называем self.findMedianInLargeFile(numbers,k,max(result+1,guess),right).Почему мы называем max(result+1, guess) как left?

c) когда count > k, почему мы используем result как right?

class Solution:

def findMedianInLargeFile(self, numbers,k,left,right):

    if left >= right:
        return left

    result = left
    guess = (left + right ) // 2
    count = 0

    # count the number that is less than guess

    for i in numbers:
        if i <= guess:
            count+=1
            result = max(result,i)

    if count == k:
        return result
    elif count < k: # if the number of items < guess is < K
        return self.findMedianInLargeFile(numbers,k,max(result+1,guess),right)
    else: 
        return self.findMedianInLargeFile(numbers,k,left,result)



def findMedian(self, numbers):
    length = len(numbers)

    if length % 2 == 1: # odd
        return self.findMedianInLargeFile(numbers,length//2 + 1,-999999999,999999999)
    else:
        return (self.findMedianInLargeFile(numbers,length//2,-999999999,999999999) + self.findMedianInLargeFile(numbers,length//2 +1 ,-999999999,999999999)) / 2

Answer 1

Вы можете выполнить сортировку слиянием с - O (nlogn) - на внешней памяти, так как она реализована для последовательной работы с данными.

Интересное решение может быть через дерево статистики заказов, с реализацией, доступной здесь: Медиана большого количества чисел для каждого набора данного размера

однако,если есть вопросы - дайте мне знать!

Answer 2

Это просто двоичный поиск по медианному значению

Сравнить с примером кода

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

• if left >= right: останавливает итерации, когда границы сталкиваются

• когда count < k, мы вызываем self.findMedianInLargeFile(numbers,k,max(result+1,guess),right), потому что наше предположение было слишком маленьким, а медианное значение больше, чем запрашиваемое значение.

• похоже, но перевернутоситуация для else чехол