العودية والتقسيم والتغلب والاختيار

def divide_max(values):
    if not values:
        raise ValueError("Maximum requires nonempty input")
    def solve(left, right):
        if right - left == 1:
            return values[left]
        middle = left + (right - left) // 2
        a = solve(left, middle)
        b = solve(middle, right)
        return a if a >= b else b
    return solve(0, len(values))

print(divide_max([-8, -2, -5, -9]))
print(divide_max([7]))

-2
7

يتقلص المجال دون تخصيص قوائم فرعية. ويوضح المدخل السالب كله لماذا تكون قيمة أساس صفرية اعتباطية خاطئة.

def select_k(values, k):
    if not 0 <= k < len(values):
        raise ValueError("k is outside the input")
    work = list(values)
    while True:
        pivot = work[0]
        lower = [value for value in work if value < pivot]
        equal = [value for value in work if value == pivot]
        higher = [value for value in work if value > pivot]
        if k < len(lower):
            work = lower
        elif k < len(lower) + len(equal):
            return pivot
        else:
            k -= len(lower) + len(equal)
            work = higher

print(select_k([7, 2, 2, 9, 4], 2))
print(select_k([3, 3, 3], 1))

4
3

تنسخ الشيفرة القوائم وتقسمها، مع حفظ مدخل المستدعي. وهي خوارزمية اختيار تعليمية واضحة خارج الموضع، وليست تنفيذا محسنا يعمل في موضعه.