[Python]이진탐색 재귀함수로 구현해보기(recursion binary search)

이번 글에서는 파이썬 언어를 사용하여 재귀함수 기반 이진탐색을 구현합니다.

1. 이진탐색으로 같은 값 찾기

문제

리스트와 목표값이 주어졌을 때 값이 존재한다면 인덱스를 반환하고 없다면 -1을 반환해라.
이때 리스트는 정렬되어 있다.

def binary_search(lst,start_p,end_p,target):
    mid_p = (start_p+end_p)//2 # 중앙 포인트 생성
    #전체 탐색후 값이 없다면 -1 반환
    if start_p>=end_p:
        return -1
    # 중앙값이 목표값이라면 해당 인덱스 반환
    if lst[mid_p] == target:             
        return mid_p 
    # 목표값보다 중앙값이 크다면 시작값부터 중앙값 이전까지 다시 탐색
    elif target < lst[mid_p]:            
        return binary_search(lst,start_p,mid_p,target)
    # 중앙값 보다 목표값이 크다면 중앙값 이후에 대해 다시 탐색
    else:                                
        return binary_search(lst,mid_p+1,end_p,target)

lst = [1,2,3,4,5]
target = 3
print(binary_search(lst,0,len(lst),target))
#=> 2

lst = [1,2,3,4,5]
target = 6
print(binary_search(lst,0,len(lst),target))
#=> -1

lst = [2,3,4,5,6]
target = 1
print(binary_search(lst,0,len(lst),target))
#=> -1

lst = [2,3,4,5,6]
target = 5
print(binary_search(lst,0,len(lst),target))
#=> 3

리스트의 start point와 end point 조정하며 이진탐색을 수행한다.

같은 값을 찾는 문제이므로 lst[mid_p]와 target이 일치하지 않는다면 lst[mid_p]의 값을 배제하고 그 이전 또는 이후에서 탐색을 다시 시작하면 된다.

 

2. 이진탐색으로 가장 근사한 값 찾기

리스트와 목표값이 주어졌을 때 같은 값 또는 가장 근사한 값을 반환해라.

근사한 값이 2개 존재한다면 그중 작은 값을 반환해라.
(ex: target:7, list[5,6,8,9] 일때 6과8 모두 1차이로 7과 근사하다. 이때 더 작은 값인 6 반환)
이때 리스트는 정렬되어 있다.

def binary_search_similar(lst,start_p,end_p,target):
    mid_p = (start_p+end_p)//2 # 중앙 포인트 생성
    
    print(start_p,mid_p,end_p)
    
    # 분할된 리스트의 길이가 2 이하일 때
    # 비교를 통해서 근사한 값을 찾는다
    if end_p-start_p <=2:
        if abs(lst[start_p]-target)<=abs(lst[end_p-1]-target):
            return lst[start_p]
        else:
            return lst[end_p-1]
    
    # 중앙값이 목표값이라면 해당 인덱스 반환
    if lst[mid_p] == target:             
        return lst[mid_p] 
    # 목표값보다 중앙값이 크다면 시작값부터 중앙값까지 다시 탐색
    elif target < lst[mid_p]:            
        return binary_search_similar(lst,start_p,mid_p+1,target)
    # 중앙값 보다 목표값이 크다면 중앙값부터 다시 탐색
    else:                                
        return binary_search_similar(lst,mid_p,end_p,target)

lst = [2,4,6,8,10]
target = 1
print(binary_search_similar(lst,0,len(lst),target))
#=> 2

lst = [2,4,6,8,10]
target = 3
print(binary_search_similar(lst,0,len(lst),target))
#=> 2

lst = [2,3,4,5,6]
target = 7
print(binary_search_similar(lst,0,len(lst),target))
#=> 6

lst = [1,3,5,7]
target = 2
print(binary_search_similar(lst,0,len(lst),target))
#=> 1

앞서 같은값 찾기와 비슷하지만 다른점들이 존재한다.

일단 근사한 값을 찾기 때문에, 재귀함수를 호출할 때  lst[mid_p]의 값을 배제하면 안된다.

또한 함수 종료조건이 탐색대상 리스트의 구간 길이가 2이하일때(end_point-start_point<=2) 가장 근사한 값을 찾아 반환한다.

※ 처음에 end point가 리스트의 길이로 입력되었으므로 end point 호출을 하여 out of index 에러를 방지하기 위해서 -1을 취해주었다.