검색 알고리즘 - 이진 검색

이진 검색 알고리즘을 사용하기 위한 조건

→ 배열의 데이터가 정렬되어 있어야 한다.

이 조건을 만족한다면 이진 검색은 선형 검색보다 빠르게 검색할 수 있다.

 

따라서 이진 검색은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다.

 

이진 검색 알고리즘의 작동 원리

검색 범위의 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl, pr, pc라고 칭하고,

검색을 시작할 때 pl은 0, pr은 n - 1, pc는 (n - 1) // 2로 초기화한다.

(pl은 배열의 맨 앞, pr은 배열의 맨 끝, pc는 배열의 중간의 인덱스를 잡아줘야 하기 때문)

 

1. a[pc] < key 일 때(배열 중간의 인덱스 값이 더 작다 = 찾는 값이 우측에 있다)

a[pl]~a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외한다.

검색 범위는 중앙 원소 a[pc]보다 뒤쪽인 a[pc+1] ~ a[pr]로 좁혀진다.

따라서 pl 값을 pc + 1로 업데이트 할 수 있다.

 

2. a[pc] > key 일 때(배열 중간의 인덱스 값이 더 크다 = 찾는 값이 좌측에 있다)

a[pc]~a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외한다.

검색 범위는 중앙 원소 a[pc]보다 앞쪽인 a[pl] ~ a[pc]로 좁혀진다.

따라서 pr 값을 pc - 1로 업데이트 할 수 있다.

 

이진 검색 알고리즘의 종료 조건

1) a[pc]와 key가 일치하는 경우(검색에 성공한 경우)

2) 검색 범위가 더 이상 없는 경우(검색에 실패한 경우)

 

이진 검색 알고리즘을 이용해 검색하는 코드

# 이진 검색 알고리즘

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any) -> int:
    """시퀀스 a에서 key와 일치하는 원소를 이진 검색"""
    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('원소 수를 입력하세요.: '))
    x = [None] * num    # 원소 수가 num인 배열을 생성

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

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

    for i in range(1, num):
        while True:
            x[i] = int(input(f'x[{i}]: '))
            if x[i] >= x[i - 1]:
                break   # 바로 직전에 입력한 원솟값보다 큰 값을 입력

    ky = int(input('검색할 값을 입력하세요.: '))  # 검색할 키값 ky를 입력

    idx = bin_search(x, ky) # ky값과 같은 원소를 x에서 검색

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

 

이진 검색에서는 검색 대상 배열이 오름차순(or 내림차순)으로 정렬되어 있어야 하며,

위 코드 중 while 문에서는 바로 앞에 입력한 원소보다 큰 값을 입력받도록 유도한다.

만약 바로 앞에 입력한 원소보다 작은 값을 입력하면 다시 입력하게 된다.(무한루프로 동작)

 

이진 검색 알고리즘은 반복할 때마다 검색 범위가 거의 절반으로 줄어들므로 검색하는 데 필요한 비교 횟수는 평균 log n이다. 검색에 실패한 경우는 log(n + 1)번이며, 검색에 성공할 경우는 log n - 1번이다.

 

 

이진 검색의 실행 과정 출력하기

# 이진 검색 알고리즘의 실행 과정을 출력

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any) -> int:
    """시퀀스 a에서 key와 일치하는 원소를 이진 검색(실행 과정을 출력)"""
    pl = 0  # 검색 범위 맨 앞 원소의 인덱스
    pr = len(a) - 1 # 검색 범위 맨 끝 원소의 인덱스

    print('   |', end='')
    for i in range(len(a)):
        print(f'{i : 4}', end='')
    print()
    print('---+' + (4 * len(a) + 2) * '-')

    while True:
        pc = (pl + pr) // 2 # 중앙 원소의 인덱스

        print('   |', end='')

        if pl != pc:    # pl 원소 위에 <-를 출력
            print((pl * 4 + 1) * ' ' + '<-' + ((pc - pl) * 4) * ' ' + '+', end='')
        else:
            print((pc * 4 + 1) * ' ' + '<+', end='')
        if pc != pr:    # pr 원소 위에 ->를 출력
            print(((pr - pc) * 4 - 2) * ' ' + '->')
        else:
            print('->')
        print(f'{pc:3}|', end='')
        for i in range(len(a)):
            print(f'{a[i]:4}', end='')
        print('\n   |')

        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('원소 수를 입력하세요.: '))
    x = [None] * num    # 원소 수가 num인 배열을 생성

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

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

    for i in range(1, num):
        while True:
            x[i] = int(input(f'x[{i}]: '))
            if x[i] >= x[i - 1]:   # 바로 직전에 입력한 원솟값보다 큰 값을 입력
                break

    ky = int(input('검색할 값을 입력하세요.: '))  # 검색할 키값 ky를 입력

    idx = bin_search(x, ky) # ky값과 같은 원소를 x에서 검색

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

 

실행결과

원소 수를 입력하세요.: 11
배열 데이터를 오름차순으로 입력하세요.
x[0]: 1
x[1]: 2
x[2]: 3
x[3]: 4
x[4]: 5
x[5]: 6
x[6]: 7
x[7]: 8
x[8]: 9
x[9]: 10
x[10]: 11
검색할 값을 입력하세요.: 8
   |   0   1   2   3   4   5   6   7   8   9  10
---+----------------------------------------------
   |  <-                   +                  ->
  5|   1   2   3   4   5   6   7   8   9  10  11
   |
   |                          <-       +      ->
  8|   1   2   3   4   5   6   7   8   9  10  11
   |
   |                          <+   ->
  6|   1   2   3   4   5   6   7   8   9  10  11
   |
   |                             <+->
  7|   1   2   3   4   5   6   7   8   9  10  11
   |
검색값은 x[7]에 있습니다.

Process finished with exit code 0