algorithm.py

# N binary_search
# I {"version": "1.0", "typing": ["Callable"]}
def binary_search(beg: int, end: int, predicate: Callable[[int], bool]) -> int:
    """Returns the minimum int X in [beg, end) where predicate(X) is true."""
    if not predicate(end - 1):
        raise ValueError
    while beg < end:
        mid = (beg + end) // 2
        if predicate(mid):
            end = mid
        else:
            beg = mid + 1
    return beg

• 최소값, 즉 predicate(x)가 x<t에서 False 이고 x>=t에서 True일때, t를 리턴해주는 함수이다.
• 만약 반대로 최대값, 즉 predicate(x)가 x⇐t에서 True 이고 x>t에서 False일 때, t를 구해야 한다면, predicate를 negate시키고, 찾아진 값에서 1을 빼줌으로써 구할 수 있다.
  • x = binary_search(beg, end, lambda(x): not predicate(x)) - 1

T = TypeVar('T')


# N nth_element
# I {"version": "1.0", "typing": ["Sequence, TypeVar"], "const": ["T"]}
def nth_element(arr: Sequence[T], n: int, threshold: int = 500_000) -> T:
    """Returns n-th smallest element from given sequence."""
    def nth_element_rec(arr, n):
        if len(arr) <= threshold:
            return sorted(arr)[n - 1]        
        pivot = sorted([arr[0], arr[-1], arr[len(arr) // 2]])[1]    
        sub = [el for el in arr if el < pivot]
        if n <= len(sub):
            return nth_element_rec(sub, n)
        sub = [el for el in arr if el > pivot]
        if (l := n - (len(arr) - len(sub))) > 0:
            return nth_element_rec(sub, l) 
        return pivot       
    
    if not 1 <= n <= len(arr):
        raise ValueError(f'n({n}) must be in [1, {len(arr)}]')
    return nth_element_rec(arr, n)

• QuickSelect 알고리즘. 피벗은 median of 3로 구한다
• 선택 알고리즘 참고
• 시퀀스의 길이가 아주 클때에만 (적어도 500,000 이상) 사용할 가치가 있고, 그렇지 않으면 그냥 전체를 sorting해서 구하는 것이 더 효율적이다.