[파이썬] 이진탐색 구현하기

실습 설명

‘이진 탐색(Binary Search)’ 알고리즘을 사용해서 어떤 원소가 리스트 안에 포함되어 있는지 확인하려고 합니다. 이진 탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 합니다. 정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능합니다.

왜 이 알고리즘의 이름이 ‘이진 탐색’일까요? 1회 비교를 거칠 때마다 탐색 범위가 (대략) 절반으로 줄어들기 때문입니다.

예를 들어 [1, 2, 3, 5, 8, 13, 21, 34, 55]에서 3을 찾는 경우, 알고리즘의 진행 방식은 다음과 같습니다:

시도 1

리스트의 첫 번째 인덱스와 마지막 인덱스의 값을 합하여 2로 나눈 후, 중간 인덱스로 지정합니다. 그리고 그 인덱스에 해당하는 값이 3인지 확인해 봅니다.

이 경우 리스트의 첫 번째 인덱스는 0이고 마지막 인덱스는 8이기 때문에, 중간 인덱스는 4이고 해당 원소는 8입니다. 찾고자 하는 원소(3)는 중간 원소(8)에 비해 작습니다. 리스트는 정렬되어 있으니, 이제 인덱스 4~8은 탐색 범위에서 제외시킬 수 있습니다. 탐색 범위가 절반으로 줄어든 것이죠.

시도 2

탐색 범위는 이제 인덱스 0~3입니다. 탐색 범위의 첫 번째 인덱스는 0이고 마지막 인덱스는 3이기 때문에, 중간 인덱스는 (0 + 3) // 2인 1입니다. 인덱스 1에 해당하는 원소는 2이죠.

찾고자 하는 원소(3)는 중간 원소(2)에 비해 큽니다. 리스트는 정렬되어 있으니, 이제 인덱스 0~1은 탐색 범위에서 제외시키면 됩니다. 탐색 범위가 다시 절반으로 줄어든 것이죠.

시도 3

탐색 범위는 이제 인덱스 2~3입니다. 탐색 범위의 리스트의 첫 번째 인덱스는 2이고 마지막 인덱스는 3이므로, 중간 인덱스는 (2 + 3) // 2인 2입니다. 인덱스 2에 해당하는 원소의 값은 3이죠.

찾고자 하는 원소(3)는 중간에 해당하는 원소(3)와 일치합니다. 값을 찾았으니, 인덱스 2를 리턴해 주며, 알고리즘을 종료합니다.

def binary_search(element, some_list):
    # 여기에 코드를 작성하세요
    some_list.sort()
    str_idx = 0
    end_idx = len(some_list)-1
    
    while str_idx <= end_idx:
        mid_idx = (str_idx + end_idx) // 2
        # mid_idx = int(str_idx + end_idx/2)
        
        if some_list[mid_idx] == element:
            return mid_idx
        elif some_list[mid_idx] > element:
            end_idx = mid_idx - 1
        elif some_list[mid_idx] < element:
            str_idx = mid_idx + 1
   
    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]))

0
None
2
1
4

 

이진 탐색 구현해보기 - 좋은 알고리즘이란? | 코드잇