배열 검색 - 이진 검색

이진 검색

 

배열의 데이터가 정렬 되었을 때 배열의 첫번째 원소부터 하나씩 스캔하는 선형 검색보다 빠르게 검색할 수 있는 알고리즘입니다. 즉, 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있습니다.

 

n개의 원소가 오름차순으로 정렬된 배열 seq에서 이진 검색하는 알고리즘은 검색 범위의 맨 앞(pl), 맨 끝(pr), 중앙의 인덱스(pc)를 활용하여 검색합니다.

검색할 키 값이 정렬된 배열의 중앙 값을 기준으로 앞 혹은 뒤인지를 반복문 안에서 인덱스 변수 값을 갱신해나가며 키 값을 찾을 때까지 검색해나가는 것입니다.

 

예를 들어 seq = [5, 7, 10, 12, 14, 16, 20] 배열에서 이진 검색 알고리즘을 토대로 키 값 16을 검색하겠습니다. 

이때 pl = 0, pr = 6, pc = 3입니다. 

 

seq[pc] = 12입니다. 12 < 16 이므로 오름차순으로 정렬된 배열 seq에서는 pc보다 큰 인덱스의 seq에 값이 있을 것입니다. 이때 세 가지 인덱스 변수들을 갱신합니다.

pl = 4(이전 pc + 1), pr = 6(유지), pc = (pl + pr) / 2 = 5

 

seq[pc] = 16이므로 키 값을 찾았습니다. 

 

이렇듯 이진 검색을 한 단계씩 진행할 때마다 검색 범위는 거의 반으로 좁혀집니다. 즉, 필요한 비교 횟수는 평균 log n 입니다. 

 

앞서 설명한 예제를 구현해보도록 하겠습니다. 마찬가지로 배열 seq는 오름차순으로 정렬되어 있다는 가정하에 값을 오름차순으로 대입하도록 하겠습니다.

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any) -> int:
    pl = 0           # 검색 범위 맨 앞 원소의 인덱스
    pr = len(a) - 1  # 검색 범위 맨 끝 원소의 인덱스

    while True:
        pc = (pl + pr) // 2  # 중앙 원소의 인덱스
        if a[pc] == key:
            return pc    # 검색 성공
        elif a[pc] < key:
            pl = pc + 1  # 검색 범위를 뒤쪽의 절반으로 좁힘
        else:
            pr = pc - 1  # 검색 범위를 앞쪽의 절반으로 좁힘
        if pl > pr:
            break
    return -1            # 검색 실패

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요.: '))
    seq = [None] * num

    print('배열 데이터를 오름차순으로 입력하세요.')

    seq[0] = int(input('seq[0]: '))

    for i in range(1, num):
        while True:
            seq[i] = int(input(f'seq[{i}]: '))
            if seq[i] >= seq[i - 1]:
                 break

    k = int(input('검색할 값을 입력하세요.: '))

    idx = bin_search(seq, k)

    if idx < 0:
        print('원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

"""
원소 수를 입력하세요.: 3
배열 데이터를 오름차순으로 입력하세요.
seq[0]: 1
seq[1]: 34
seq[2]: 667
검색할 값을 입력하세요.: 34
검색값은 x[1]에 있습니다.
"""

 

출처

 

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편