[Python] 이진 탐색(Binary Search)

이진 탐색(Binary Search)

이진 탐색

원리

• 정렬된 데이터 집합을 검색하는 경우에는 이진 탐색(Binary Search)을 주로 사용하는데, 순차 탐색에 비해서 엄청난 성능으로 데이터를 검색할 수 있다.
• 이진 탐색은 전체를 반씩 잘라내서 한쪽을 버리는 방식을 사용한다.
• 데이터 개수가 계속 1/2씩만 남으므로 급격히 비교할 데이터 개수가 줄어든다.
• 찾는 값을 검색하고자 1단계에서 중앙 위치를 기준으로 잡는다.
  • 찾는 값이 왼쪽 구역에 있을 경우, 오른쪽 구역을 버린다.
    • 이 과정을 찾을 값을 찾을 때까지 반복한다.

 

구현

• 이진 탐색 구현은 키를 찾기 위해 계속 시작, 중앙, 끝을 반복적으로 1/2씩 줄여 가면서 계산하는 방식이다.
• 검색할 범위를 1/2씩 반복해서 분할하는 기법을 분할 정복(Divide and Conquer)이라고 한다.

① 전체의 첫 데이터를 '시작'으로 지정하고, 마지막 데이터를 '끝'으로 지정한 후, 시작과 끝의 중앙인 데이터를 찾을 값과 비교한다.
② 끝은 그대로 두고 시작을 중앙의 바로 오른쪽으로 옮긴다.
③ 중앙의 오른쪽 그룹에서 다시 시작과 끝의 1/2 위치인 새 중앙을 찾을 값과 비교한다.
④ 시작은 그대로 두고 끝을 중앙의 바로 왼쪽으로 옮긴다.
⑤ 중앙의 왼쪽 그룹에서 다시 시작과 끝의 1/2 위치인 새 중앙을 찾을 값과 비교한다.
...(②~⑤ 과정 반복)
⑥ 검색 성공/실패

시작 = 0
끝 = 배열길이 - 1
while (시작 <= 끝)
    중앙 = (시작+끝) // 2
    if 찾는값 == 중앙 :
        검색 성공. 중앙 위치 반환
    elif 찾는값 > 중앙 :
        시작 = 중앙 + 1
    else :
        끝 = 중앙 - 1
while 문에서 중앙 위치를 반환하지 못하고, 여기까지 오면 검색 실패

 

구현

def binSearch(ary, fData) :
    pos = -1
    start = 0
    end = len(ary) - 1

    while (start <= end) :
        mid = (start + end ) // 2
        if fData == ary[mid] :
            return mid
        elif fData > ary[mid] :
            start = mid + 1
        else :
            end = mid - 1

    return pos

dataAry = [ 50, 60, 105, 120, 150, 160, 162, 168, 177, 188]
findData = 162  # 할머니키

print('배열 -->', dataAry)
position = binSearch(dataAry, findData)
if position == -1 :
    print(findData,'(이)가 없네요.')
else :
    print(findData,'(은)는 ', position, '위치에 있음')

 

배열 --> [50, 60, 105, 120, 150, 160, 162, 168, 177, 188]
162 (은)는  6 위치에 있음

 

이진 탐색의 시간 복잡도

• 이진 탐색의 데이터 개수를 1/2로 줄여 가면서 비교한 시간 복잡도는 `O(log_{2}n)`이 된다.
  • `O(n)`에 비해 엄청나게 효과적인 방식이다.