검색 알고리즘-이진검색(Binary Search)

이진 검색(Binary search)

이진 검색은 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행한다.

이진 검색 알고리즘을 사용하려면 배열의 데이터가 정렬되어 있어야 하고 이진 검색은 선형 검색보다 빠르게 검색할 수 있다는 장점이 있다. 

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

이진 검색 그림 예시

 

이진 검색의 검색 범위의 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl,pr,pc라고 하고 중앙 값부터 검색 범위를 계속 좁혀가면 된다. 

# binary search 이진검색 알고리즘

from typing import Any,Sequence

def bin_search(a:Sequence, key:Any) -> int:
    """sequence 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 # fail search

if __name__=='__main__':
    num=int(input('원소수를 입력하세요: '))
    x = [None] * 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('put the value: '))

    idx = bin_search(x,ky)

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