2021-10-07 이진탐색 재귀 반영환

 

이진탐색 알고리즘은 start idx와 end idx로 범위를 지정해놓고, mid idx로 값을 찾아가며 탐색 범위를 1/2씩 줄여나가는 알고리즘이다. 

 

즉 원본 리스트를 절반씩 나누어 가면서 범위를 줄여나가는게 목표인데

재귀를 이용하려면 절반씩 나누는 과정을 재귀적으로 진행하면 될 것 같다.

1. 값을 찾으면 그 index 리턴 <- base case
2. 리스트 내에 값이 없으면 종료를 시켜야 하는데, start idx 는 항상 end idx보다 작아야하므로 start idx > end idx면 종료

def binary_search(element, some_list, start_index=0, end_index=None):
    
    if end_index == None:
        end_index = len(some_list) - 1
    
    if start_index > end_index:
        return None
        
    mid = (start_index + end_index) // 2
    
    if element == some_list[mid]:
        return mid
    # base case
    
    if element > some_list[mid]:
        return binary_search(element, some_list, mid +1, end_index)
    if element < some_list[mid]:
        return binary_search(element, some_list, start_index, mid -1)
    # recursive case