[python] binary search tree

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

def bsearch(items, key):
    # recursive function을 독립 시키기 위한 adapter function
    return bs_helper(items, key, -1, len(items))
 
def bs_helper(items, key, lower, upper):
    # Base condition : 값을 못 찾았을 경우
    if lower + 1 == upper:
        return None
    mid = (lower + upper) // 2
    # 값을 찾았을 경우 return
    if key == items[mid]:
        return mid
    # 아래 쪽에 위치할 경우 lower range 를 검색
    if key < items[mid]:
        return bs_helper(items, key, lower, mid)
    else:
        return bs_helper(items, key, mid, upper)
 
 
a = [1, 2, 4, 5, 7, 9, 10, 34, 45, 89, 345]
print(bsearch(a, 5))