2.2 이분 탐색 (Binary Search)

이분탐색이란?

 

이분탐색은 정렬되어 있는 배열에서 사용 가능한 탐색 방법으로, 탐색 범위를 매번 반으로 쪼개 나가며 탐색하는 방법을 얘기합니다.

 

일반적인 탐색 방법과 비교하기 위해 다음과 같은 문제를 예시로 들어봅시다.

 

1~N 사이의 자연수로 이루어진 길이가 N인 수열이 있습니다. 이 수열에서 1 이상 N 이하의 정수 K는 몇 번째에 위치해 있는지 구하고자 합니다.

 

이를 완전탐색으로 해결하면 1번째 값부터 N번째 값까지 일일이 확인해보는 O(N)의 방법이 있습니다.

 

하지만 N이 100,000 이상 혹은 더욱 커지면 비효율적으로 동작하므로 더욱 빠르게 동작하는 알고리즘이 필요합니다.

만약 수열이 오름차순으로 정렬되어 있다면 이분탐색이라는 알고리즘을 적용할 수 있고, 이의 시간복잡도는 O(logN)입니다.

 

이분 탐색의 동작 과정은 다음과 같습니다.

 

• 먼저 배열의 중앙에 있는 값 선택하고, 선택한 값과 내가 찾을 값 비교한다.
• 만약 중앙에 있는 값이 내가 찾고 있는 값보다 크면 1~(중앙-1)으로 탐색범위를 바꿔서 다시 탐색하고,
• 만약 중앙에 있는 값이 내가 찾고 있는 값보다 작다면 (중앙+1)~N으로 탐색범위를 바꿔서 다시 탐색한다.  

 

이 과정을 중앙에 있는 값이 내가 찾는 값과 같으면 종료합니다.

 

 

 

 

예를 들어 [1,2,3,4,5,6,7,8,9,101,2,3,4,5,6,7,8,9,10]인 배열에서 7을 찾으려고 할 때 그냥 반복문을 이용해 1번째부터 N번째까지 탐색을 하면 O(N)으로 구할 수 있습니다. 

 

하지만 이분탐색을 이용하면 O(logN)의 시간복잡도를 가지게 됩니다. 만약 데이터 수가 10억개 정도일때 반복문을 써서 하나씩 확인하면 최악의 경우에 10억번 계산하게 되지만 이분탐색으로는 30여번 만에 계산이 끝나게 된다는 뜻입니다.

 

처음에 배열의 중간에 있는 값은 5

 

내가 찾는 값은 5보다 크므로 나는 이제 [6,7,8,9,10]만 탐색합니다. 

[6,7,8,9,10]의 중간에 있는 값은 8입니다.

 

내가 찾는 값은 8보다 작으므로 나는 이제 [6,7]만 탐색합니다.


[6,7]의 중간에 있는 값은 6입니다.

 

우리가 찾는 값은 6보다 크므로 나는 이제 [7]만 탐색합니다. 

 

7을 찾았습니다! 

 

이분 탐색은 항상 정렬된 데이터에서만 사용이 가능합니다.

 

이분 탐색에서 탐색 범위 [s, e]에서 중앙값을 mid라고 했을 때, 배열의 mid번째 값이 내가 찾고자 하는 값보다 크다면 mid번째보다 더 뒤에 있는 값들은 모두 내가 찾고자 하는 값보다 클 것입니다.

 

따라서 우리는 [mid, e]의 구간을 무시할 수 있게 되고, 이 때 이분탐색을 사용할 수 있기 때문입니다.

 

만약 구간 [mid, e]에 하나라도 내가 찾고자 하는 값보다 크지 않은 값이 존재한다면 그 구간에도 내가 찾고자 하는 값이 존재할 가능성이 있기 때문에 이분탐색을 사용할 수 없습니다.

 

 

시간 복잡도가 O(logN)인 이유

 

여기서 log는 log₂입니다. 단계마다 탐색 범위를 반으로(÷2) 나누는 것과 동일하므로 이러한 시간 복잡도를 가지게 됩니다.

예를 들어 처음 데이터의 개수가 32개라면, 이론적으로 1단계를 거치면 약 16개의 데이터가 남고, 2단계에서 약 8개, 3단계에서 약 4개의 데이터만 남게 됩니다.

 

즉, 이진 탐색(이분 탐색)은 탐색 범위를 절반씩 줄이고, O(logN)의 시간 복잡도를 보장한다는 것입니다.

 

 

구현

 

탐색 범위를 설정하기 위한 변수 s, e가 필요하다. 구간 [s, e]를 줄여나가면서 탐색을 진행합니다.

 

[s, e]는 초기에 [1, N]이고, 이의 중간값인 mid는 (N+1)/2입니다. 배열의 (N+1)/2번째 값과 내가 탐색할 값을 비교하여 탐색 범위를 줄입니다.

 

n = int(input())
arr = list(map(int, input().split()))

K = int(input())
s, e = 1, n

while s <= e:
    mid = (s + e) // 2
    if arr[mid] == K:
        print("값을 찾음")
        break
    elif arr[mid] > K:
        e = mid - 1
    else:
        s = mid + 1

 

 

참고 블로그

https://david0506.tistory.com/2

이분탐색(binary search)