알고리즘 - 이진 검색

선형 검색에 이어 이진 검색입니다.

 

이진 검색은 배열을 정렬시켜야 하며 선형검색 보다 더 빠르게 검색할 수 있습니다.

이진 검색은 배열의 중앙 원소에 집중한다고 생각하면 됩니다.

 

11

24

37

41

53

72

88

위와 같이 오름차순으로 정렬된 배열이 있을 때, 숫자 24를 찾는다고 가정합니다.

배열 중간에 위치한 41을 기준으로 배열을 나누어 생각합니다.

 

숫자 24는 41보다 작기 때문에 41 뒤에 있는 배열은 생각하지 않고

41 앞쪽에 있는 11, 24, 37만 봅니다.

11

24

37

 

앞쪽 배열만 가지고 오면 지금 찾고 있는 숫자인 24가 중앙에 위치하게 됩니다.

이렇게 현재 찾는 숫자의 인덱스를 알 수 있습니다.

 

 

이진검색 코드

from typing import Any, Sequence

def bsearch(x: Sequence, key: Any):
    pl = 0  # 배열의 맨 앞 인덱스
    pr = len(x) - 1  # 배열의 맨 뒤 인덱스

    while True:
        pc = (pl + pr) // 2  # 배열의 중간 인덱스
        if x[pc] == key:
            return pc
        elif x[pc] > key:
            pr = pc - 1
            # 찾는 값이 중앙값 보다 작으면 검색 배열의 끝 값을 중간 인덱스에서 -1 해줍니다.
        else:
            pl = pc + 1
            # 찾는 값이 중앙값 보다 크면 검색 배열의 시작 값을 중간 인덱스에서 +1 해줍니다.
        if pl > pr:
            break
            '''
            만약 찾는 값이 없으면 반복문이 계속 돌아가게됩니다.
            그래서 시작값이 끝값보다 커지면 반복문을 종료시키고 -1를 리턴시킵니다.
            '''
    return -1

print('이진검색\n')

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

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

ky = int(input('검색할 숫자를 입력하세요.: '))

result = bsearch(x, ky)

if result == -1:
    print('검색값을 가지는 원소가 없습니다.')
else:
    print(f'검색 원소는 x[{result}]에 있습니다.')

 

결과창

이진검색 결과