====== algorithm.py ======

===== binary_search =====

<WRAP center round important 60%>
이 함수는 deprecated 되었습니다. [[:ps:이진 검색#bisect_모듈을_이용한_파라메트릭_서치_구현]]을 참고해서 구현하세요
</WRAP>


==== 코드 ====
<dkpr 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
</dkpr>

==== 설명 ====
  * 최소값, 즉 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 

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[binary_search]*
csv: 0
----

===== nth_element =====

==== 코드 ====
<dkpr py>
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)
</dkpr>

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

==== 이 코드를 사용하는 문제 ====
{{topic>ps:teflib:nth_element&nouser&nodate}}