[Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

 

[ Contents ]

 

 

1. 이진탐색 (Binary Search, 이분탐색)

이진탐색: 정렬된 자료를 절반씩 나누어서 탐색하는 방법

 오름차순(또는 내림차순)으로 정렬된 자료에서 사용합니다. 찾고자 하는 숫자와 자료의 중간값과 비교하여 탐색 범위를 절반씩 줄여갑니다. 찾고자 하는 수보다 작으면 작은 쪽을, 크면 큰 쪽을 찾습니다.

 

 

이진탐색 과정
1) 찾는 값과 중앙값을 비교합니다.
2) 중앙값과 같다면 탐색 종료. 작다면 작은 쪽을 크다면 큰 쪽을 찾습니다.
3) 값을 찾을 때까지 1, 2 과정을 반복합니다.

 예를 들어 32를 찾고자 한다면, 중앙값인 63과 값을 비교합니다. 63보다 작으니, 작은 쪽에서 찾습니다. 12, 32, 41의 중앙값은 '32'입니다. 32를 찾았으므로 종료합니다.

 

 

 

2. 이진탐색 예시: Up Down Game

 이진 탐색의 유명한 예시는 '업 다운 게임'입니다. 1부터 50까지 중 상대방이 생각한 숫자를 최대한 적은 횟수로 맞춰야 합니다. 제시한 숫자가 생각한 숫자보다 작으면 "UP"을, 크면 "Down"을 외칩니다.

 이 게임의 최적 전략은 '이진탐색'입니다. 중앙값을 부르면, 1번 시도할 때마다 범위가 절반씩 좁혀집니다.

 생각한 수가 17이라고 할 때, 26(1회) => 13(2회) => 20(3회) => 17(4회)로 4번 만에 맞출 수 있습니다. 최악의 경우라도 6번 만에 맞출 수 있을 정도로 성능이 좋습니다. ( 최대 시행 횟수는 log_2의 N )

 

 

 

3. 코드

#이진 탐색(자료, 찾는 값)
def binarySearch(lst, x):
    start = 0
    end = len(lst)-1

    while start <= end:
        mid = (start + end)//2 # 중앙위치
        if x == lst[mid]: # 중앙값이 찾는 값
            return mid
        elif x > lst[mid]: # 중앙값보다 큰 경우
            start = mid + 1
        else:
            end = mid - 1 # 중앙값보다 작은 경우
    return -1 # 찾지 못한 경우

 이진탐색의 과정을 그대로 구현하면 위와 같습니다. 찾는 값의 인덱스(위치)를 반환하며, 없을 경우 -1를 반환합니다.

 

 

 32를 찾는 예시를 이진탐색 코드로 구현해본 결과입니다. 반드시 오름차순으로 정렬된 리스트에만 사용해야 합니다.