Minimum i maksimum metodą dziel i zwyciężaj

Jednoczesne wyszukiwanie minimum i maksimum - Algorytmy: zakres rozszerzony (Python)

**Dziel i zwyciężaj**: dzielimy listę na dwie połowy, w każdej rekurencyjnie szukamy minimum i maksimum, a potem łączymy wyniki dwoma porównaniami. Jedno- i dwuelementowe fragmenty rozwiązujemy od razu.

def min_max(data, left, right):
    if left == right:
        return data[left], data[left]
    if right == left + 1:
        if data[left] < data[right]:
            return data[left], data[right]
        return data[right], data[left]
    middle = (left + right) // 2
    min1, max1 = min_max(data, left, middle)
    min2, max2 = min_max(data, middle + 1, right)
    return min(min1, min2), max(max1, max2)


data = [7, 2, 9, 4, 1, 8, 5, 6, 3]
print(min_max(data, 0, len(data) - 1))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.