파이썬 선형탐색(Linear Search), 이진탐색(Binary Search)

선형 탐색(Linear Search)

리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘

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

print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

 

 

이진 탐색(Binary Search)

이진탐색은 정렬된 리스트를 전제로 하며, 1회 비교를 할 때마다 탐색 범위가 절반(시간복잡도 : logn)으로 줄어든다.
리스트의 첫 번째 인덱스와 마지막 인덱스의 값을 합하여 2로 나눈 후, 중간 인덱스로 지정한다.
구하고자 하는 숫자가, 중간 인덱스보다 적은 경우 중간 이후 값은 검색 범위에서 제외한다.
구하고자 하는 숫자가, 중간 인덱스보다 큰 경우 중간 이전 값은 범위에서 제외한다.

 

반복문 사용 Version

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1

    while start_index <= end_index:
        # start_index 가 커지는 경우가 있으므로 (start_index + end_index) // 2
        mid_index = (start_index + end_index) // 2

        # element 가 mid_index 값과 같으면 return mid_index    
        if element == some_list[mid_index]:
            return mid_index

        # element 가 mid_index 값보다 적으면 end_index = mid_index - 1
        elif element < some_list[mid_index]:
            end_index = mid_index - 1

        # element 가 mid_index 값보다 크면 start_index = mid_index + 1
        else:
            start_index = mid_index + 1

    # 위의 조건에 만족하지 않는 경우(element가 list에 없는 경우) return None
    return None

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

재귀 사용 Version

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    # 중간 인덱스 구하기
    mid_index = (start_index + end_index) // 2

    # start_index가 end_index보다 크면 some_list안에 element는 없다
    if start_index > end_index:
        return None

    # element 가 mid_index 값과 같으면 return mid_index    
    if element == some_list[mid_index]:
        return mid_index

    # element 가 mid_index 값보다 적으면 end_index = mid_index - 1
    elif element < some_list[mid_index]:
        return binary_search(element, some_list, start_index, mid_index-1)

    # element 가 mid_index 값보다 크면 start_index = mid_index + 1
    elif element > some_list[mid_index]:
        return binary_search(element, some_list, mid_index+1, end_index)


print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))