[PYTHON] 탐색 알고리즘(선형탐색, 이진탐색)

선형 탐색

def linear_search(element, some_list):
    
    length = len(some_list)
    
    for i in range(0, length):
        if some_list[i] == element:
            return i
            
    return None

 

 

이진 탐색

비재귀 ver

def binary_search(element, some_list):
    left = 0
    right = len(some_list) - 1
    
    # 중간 인덱스
    i = (left + right) // 2 
    
    while left <= right:
        i = (left + right) // 2
        if some_list[i] == element:
            return i
        elif some_list[i] < element:
            # 찾으려는 원소가 더 클 때 중간 인덱스보다 오른쪽(큰 쪽)으로 이동
            left = i + 1
        else:
            # 찾으려는 원소가 더 작을 때 중간 인덱스보다 왼쪽(작은 쪽)으로 이동
            right = i - 1
            
    return None

재귀 ver

def binary_search(element, some_list, left=0, right=None):

    if right == None:
        right = len(some_list) - 1
        
    i = (left + right) // 2

    # base case
    if left > right:
        return None
    
    if some_list[i] == element:
        return i
        
    if some_list[i] < element:
        return binary_search(element, some_list, i + 1, right)
    else:
        return binary_search(element, some_list, left, i - 1)
        
    return None