cp_library/alg/divcon/median_of_three_fn.py

• View this file on GitHub
• Last update: 2025-05-06 22:58:43+09:00

Required by

• cp_library/alg/divcon/qselect_fn.py
• cp_library/math/median_fn.py

Verified with

• test/atcoder/arc/arc122_b_insurance_median.test.py
• test/atcoder/arc/arc182_d_increment_decrement_again_qselect.test.py

Code

import cp_library.alg.divcon.__header__

def median_of_three(A, l, r):
    '''Select pivot as median of first, middle, and last elements'''
    if r - l < 3: return l
    mid = (l+r) >> 1
    if A[mid] < A[l]:
        A[l], A[mid] = A[mid], A[l]
    if A[r-1] < A[mid]:
        A[mid], A[r-1] = A[r-1], A[mid]
        if A[mid] < A[l]:
            A[l], A[mid] = A[mid], A[l]
    return mid

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def median_of_three(A, l, r):
    '''Select pivot as median of first, middle, and last elements'''
    if r - l < 3: return l
    mid = (l+r) >> 1
    if A[mid] < A[l]:
        A[l], A[mid] = A[mid], A[l]
    if A[r-1] < A[mid]:
        A[mid], A[r-1] = A[r-1], A[mid]
        if A[mid] < A[l]:
            A[l], A[mid] = A[mid], A[l]
    return mid

Back to top page