Binary search with Python

binary_search.py

"""
Binary search must be preconditioned that arr is sorted(desc).
"""


__all__ = ['bin_search', 'binary_search', 'binary_search_recursive', 'binary_search_recursive2']


def bin_search(arr: list[int], target: int) -> int:
    """Ref: https://www.acmicpc.net/blog/view/109
    Approach: v[i] >= val
    - i increaed -> F, F, ..., F, T, T, ..., T

    자주하는 실수 1
    - lo, hi는 항상 정답의 범위를 나타낼 수 있도록 해야합니다.
       예를 들어 lo를 출력해야 하는 문제의 답이 최대 n일 때 hi = n으로 선언하거나,
       hi를 출력해야 하는 문제의 답이 최소 0일 때 lo = 0으로 선언하면 안됩니다.(hi = n + 1, lo = -1로 선언)
    """
    l, r = -1, len(arr)  # 자주하는 실수 1
    while l + 1 < r:
        m = (l + r) // 2
        if arr[m] >= target:
            r = m
        elif arr[m] < target:
            l = m

    if r >= len(arr) or arr[r] != target:
        return -1
    return r


def binary_search(arr: list[int], target: int) -> int:
    l, r = 0, len(arr) - 1
    while l <= r:
        m = (l + r) // 2
        if target > arr[m] :
            l = m + 1
        elif target < arr[m]:
            r = m - 1
        else:
            return m
    return -1


def binary_search_recursive(arr: list, target: int) -> bool:
    if len(arr) == 0:
        return False
    elif len(arr) <= 1:
        return True if arr[0] == target else False
    
    m = len(arr) // 2
    if target > arr[m]:
        return binary_search_recursive(arr[m+1:], target)
    elif target < arr[m]:
        return binary_search_recursive(arr[:m], target)
    else:
        return True


def binary_search_recursive_2(arr: list, target:int, l: int, r: int) -> bool:
    if l > r:
        return False
    
    m = (l + r) // 2
    if arr[m] > target:
        return binary_search_recursive2(arr, target, l, m-1)
    elif arr[m] < target:
        return binary_search_recursive2(arr, target, m+1, r)
    else:
        return True