검색 알고리즘 - 이진검색

검색의 종류로는 배열 검색, 연결 리스트 검색, 이진 검색 트리 알고리즘이 있다.

배열 검색의 종류로는 

 

• 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다.
• 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색을 수행한다.
• 해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서 빠른 검색을 수행한다. 
  • 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법이다.
  • 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다.

---

이진 검색 binary search

 

이진 검색은 원소가 오름차순이나 내림차순으로 정렬(sort)된 배열에 좀 더 효율적으로 검색할 수 있는 알고리즘이다. (선형 검색보다 빠르게 검색 가능)

 

 

위의 그림처럼 오름차순으로 정렬된 배열에서 76을 찾는 과정이다. 이진 검색에서는 배열의 중앙에 위치한 a[7]인 47에 주목한다. 76은 47보다 뒤에 위치한다. 그러면 검색 대상을 a[8] ~ a[14]로 좁힌다. 그다음 중앙값인 a[11]=77과 76을 비교하면 검색 대상을 a[8]~a[10]으로 좁힐 수 있다. 이제 검색해야 하는 대상은 2개고 76의 위치를 찾을 수 있다.

 

검색 범위의 맨 앞(pl), 맨 끝(pr), 중앙(pc)의 인덱스를 각각 0, n-1, (n-1)//2로 초기화한다.

 

<code>

# -- 이진 검색 알고리즘

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any):
    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
    
    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('검색할 값을 입력하세요 : '))
    idx = bin_search(x, ky)
    
    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

 

 

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