이진 탐색(이분 탐색, Binary Search)

이진 탐색은 배열 속에 내가 원하는 자료가 있는지 찾는 방법이다. 탐색 구간을 둘로 나누어 실행하며 이를 반복해나가기 때문에 이진 탐색이라고 부른다. 책을 펼쳐서 내가 원하는 페이지를 찾는 과정과 아주 비슷하다.

 

우선 길이가 10인 arr이라는 배열이 아래와 같이 있다고 해보자.

 

배열이 정렬되어있지 않기 때문에 내가 원하는 값이 어디에 어떤 규칙으로 있는지 알 수 없다. 이 배열에서 자료를 찾으려면 앞에서부터 순차적으로 찾아야 한다. 이걸 선형 탐색(Linear Search)라고 한다.

8을 찾는다면 적당히 5번의 비교로 끝나겠지만 5를 찾는 경우 최악의 상황으로 배열 내 모든 데이터를 확인해야 한다. 따라서 이 방법은 시간 복잡도가 O(n)이다. 사실 이 정도의 시간복잡도가 그리 나쁘지는 않지만 배열의 길이가 아주 길어지거나 탐색 횟수가 많아지면 문제가 된다. 배열 길이가 만약 100,000,000이라고 해보면 매 탐색마다 평균적으로 5천만 번의 비교를 해야 한다.

 

배열에 저장된 값들이 정렬되어있다면 탐색에 규칙을 부여할 수 있다.

 

정렬이 끝난 arr은 이제 인덱스가 증가함에 따라 값이 감소하는 일이 없음을 알 수 있다. 따라서 이제 어떤 위치의 값을 확인했을 때, 찾고자 하는 값보다 저장된 값이 크다면 더 앞쪽의 인덱스를 찾아보면 되고 찾고자 하는 값보다 더 작다면 더 뒤쪽의 인덱스를 찾아보면 된다. 여기서 '어떤 위치'를 탐색 범위의 한 가운데로 정하는 것이 이진 탐색의 기본 원리다.

 

정렬이 끝난 arr에서 5를 찾는 과정은 다음과 같다.

빨간 화살표는 탐색 범위의 시작이고 파란 화살표는 탐색 범위의 끝이다. 노란 화살표는 범위의 한 가운데 값을 나타낸다. 양 끝의 인덱스 평균 값인데 나누어 떨어지지 않으면 버림한다. 범위의 가운데인 arr[4]는 찾고자하는 5보다 작다. 따라서 5는 노란 화살표보다 더 뒤에 있다. 빨간 화살표를 노란 화살표의 다음 위치로 이동시킨다.(노란색으로 옮겨도 될 것 같지만 그렇게 하면 이미 확인한 곳을 또 탐색 범위에 넣게 되기 때문에 약간의 손실이 있다.)

 

새로운 탐색 범위의 가운데인 arr[7]은 5보다 크다. 따라서 이젠 노란 화살표보다 앞에 원하는 값이 있다. 파란 화살표를 노란 화살표 이전 위치로 이동시킨다.

 

탐색 범위의 가운데인 arr[5]는 5이다. 이렇게 탐색이 끝난다. 그림으로 보면 탐색 범위는 이제 2칸이다. 만약 이 위치에 5가 아니라 다른 값이 있었다면 어떻게 되어야 할까.

 

만약 arr[5] == 4라면 찾고자 하는 값이 더 크기 때문에 노란 화살표보다 뒤에 원하는 값이 있다. 이제 빨간 화살표를 노란 화살표의 다음 위치로 옮기면 탐색 범위는 1칸이 되며 더 이상 좁힐 수 없다. arr[6] == 7이므로 파란 화살표가 노란 화살표의 이전 위치인 i == 5로 올 것이다. 여기서 탐색 범위의 시작과 끝이 엇갈리게 된다. 이 경우, 모든 범위 안에서 원하는 값을 찾을 수 없는 것이기 때문에 탐색을 종료하고 원하는 값이 없음을 반환한다.

 

만약 arr[5] == 6이라면 찾고자 하는 값이 더 작기 때문에 노란 화살표보다 앞에 원하는 값이 있다. 파란 화살표를 노란 화살표 이전 위치로 옮기면 역시 마찬가지 탐색 범위의 시작과 끝이 엇갈린다. 탐색을 종료하고 원하는 값이 없음을 반환한다.

 

구현할 때는 탐색 범위의 인덱스와 중앙 인덱스 이동만 잘 맞춰주고 탐색 종료 조건을 정하면 된다.

#탐색하려는 배열: arr
#찾으려는 수 :k

def binarysearch(k):
    s = 0
    e = N - 1
    while True:
        if e < s:
            return False
        m = int((s + e) / 2)
        if arr[m] < k:
            s = m + 1
        elif arr[m] > k:
            e = m - 1
        else:
            return True

 

정렬이 되어있어야 한다는 전제 조건이 있기 때문에 항상 사용 가능한 것은 아니지만 정렬만 해낸다면 쓸 수 있다. 하지만 그렇다고 해서 이진 탐색이 선형 탐색보다 효율적이니 모든 배열을 정렬해야 하는 것은 아니다. 비용과 이익을 따져봤을 때 정렬하는 비용이 너무 크다면 꼭 이 방법을 사용할 필요는 없을 것이다. 아니면 애초에 배열을 만들 때 연결리스트와 같이 저장과 동시에 정렬하도록 하는 것도 방법이다.

 

1920번: 수 찾기