이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)

오늘 다뤄 볼 주제는 바로 "이진 탐색(Binary Search)" 입니다.

높은 효율을 자랑하며 실제로 자주 쓰이는 알고리즘인데요, 과연 이진 탐색이라는 게 무엇인지 한번 알아봅시다!

- 이진 탐색(Binary Search)

: 이진 탐색이란, 정렬된 자료를 반으로 계속해서 나누어 탐색하는 방법입니다.

쉽게 말해, 아래와 같이 자료를 계속해서 반으로 쪼개서 찾는 것이죠.

[자료 1] 이진 탐색 (Binary Search)

감이 잘 안오신다구요? 백문이 불여일견! 바로 C로 작성된 코드로 보시겠습니다~

int* binarySearch(int key, const int *target, size_t length) {
    int first = 0, last = length - 1, middle = (first + last) / 2;
    while (first <= last) {
        if (target[middle] == key) 	
            return target + middle;
            
        if (target[middle] > key) 
            last = middle - 1;
        else 			
            first = middle + 1;
            
        middle = (first + last) / 2;
    }  	
    
    return NULL;
}

자, 우선 처음부터 차근 차근 분석해보죠.

인수로는 key, target, length 를 받고 있는데요, key 는 여기서 검색할 값, target 은 검색 대상이 있는 배열, length 는 배열의 길이입니다.

그 다음 함수 내의 첫 줄에서는 int형 변수 first 와 last, middle 을 선언한 뒤 각각 초기화 해주고 있습니다.

여기서 부터가 핵심인데요, first 와 last 는 처음에는 각각 배열의 첫 번째 index, 마지막 index를 가리키고 있습니다.

middle 은 중간에 있는 index를 가리키고 있구요.

그 뒤, while 반복문으로 first가 last 보다 작은 값인 동안 계속 아래 부분이 실행이 되도록합니다.

다음으로, 배열의 중간 값이 key 값과 일치하는 지 검사를 해서 만약 일치한다면 해당 값이 있는 주소를 return 합니다.

일치하지 않는다면, key값과 비교를 해서 key 값보다 중간 값이 클 경우, last 를 middle 보다 하나 작은 값으로 바꿔주고,

key값보다 중간 값이 작을 경우, first 를 middle 보다 하나 큰 값으로 바꿔줍니다.

그리고 마지막으로, middle 값을 first 와 last 의 중간 값으로 바꿔주죠.

설명으로 봐서는 '이게 무슨 말이지...' 싶으실 테니 바로 그림으로 하나하나 다시 보도록 하겠습니다.

1. 첫 부분과 끝 부분을 가리키는 first 와 last, 중간 값을 가리키는 middle 을 초기화 합니다.

[자료 2]

2. first가 last 보다 작거나 같은 지 검사합니다.

3. first <= last 이면, middle 의 index에 위치한 값(target[middle])이 찾고자 하는 값인 지 검사합니다.

4-1. 찾고자 하는 값이라면, 해당 값이 있는 주소(target + middle)을 return 합니다.

4-2. 찾고자 하는 값이 아니라면, target[middle] 값이 찾고자 하는 값보다 큰지 비교합니다.

5-1. target[middle] > key 라면, last 의 값을 middle - 1로 변경합니다.

(찾고자 하는 값이 target[middle]보다 작다는 정보를 얻었으므로, middle 의 오른쪽 부분은 탐색할 필요가 없어졌습니다.)

(또한, middle - 1인 이유는 middle 에 위치한 값(target[middle])은

위에서 찾고자 하는 값과 일치하지 않는 다는 것을 알았기 때문이구요.)

[자료 3]

5-2. 그렇지 않다면(즉, target[middle] < key) 라면), first 의 값을 middle + 1로 변경합니다.

(찾고자 하는 값이 target[middle]보다 크다는 정보를 얻었으므로, middle 의 왼쪽 부분은 탐색할 필요가 없어졌습니다.)

(또한, middle + 1인 이유는 middle 에 위치한 값(target[middle])은

위에서 찾고자 하는 값과 일치하지 않는 다는 것을 알았기 때문이구요.)

[자료 4]

6. middle 의 값을 first 와 last 의 중간 값((first + last) / 2)으로 변경합니다.

[자료 5]

[자료 6]

7. 검색할 값을 찾을 때까지 위 과정을 반복합니다.

(first > last 가 되면 표현식의 값이 false가 되어 while 문을 벗어나게 되고, 해당하는 값이 없으므로 NULL을 return 합니다.)

단, 이진 탐색 알고리즘을 사용하실 때에 주의하실 점이 하나 있습니다.

앞에서 설명 드렸듯이, 반드시 '정렬'된 자료에만 사용하셔야 합니다.

어떤 정렬이냐구요? 여기서는 '오름차순'으로 정렬되어 있어야 정상적으로 작동합니다.

그 이유는 위에 있는 C로 작성된 코드에 숨어 있습니다.

쉽게 이해하기 위해 한 가지 상황을 가정해봅시다. 만약 위 자료가 오름차순으로 정렬되어 있지 않다면?

가령 무작위로 배치 되어있다고 가정한다면, 위에서 5, 6번을 적용하는게 과연 옳은 것일까요?

자료가 무작위로 배치되어 있기 때문에 어느 특정 방향(앞 또는 뒤)으로 간다고 해서 해당 자료가 중간 부분보다 작거나 크다는 보장이 없습니다.

따라서, 찾고자 하는 데이터를 지나치는 경우(이진 탐색의 특성 상 전체의 반만 탐색하기 때문에 나머지 반은 버려지게 되죠)가 빈번하게 발생해 자료가 있음에도 불구하고 찾지 못하게 될 수 있습니다.

이제 이 주의 사항이 확 와닿으시죠?

그렇다면 슬슬 마지막 주제로 옮겨봅시다!

(참고로 위의 코드에서 target[middle] > key 일 때와 target[middle] < key 일 때, last = middle - 1과 first = middle + 1 의 순서만 바꿔준다면 내림차순으로 정렬되어 있는 자료에 대해 탐색을 할 수 있습니다.)

마지막 주제는 알고리즘하면 놓칠 수 없는 부분이죠! 바로 '시간 복잡도 분석(Analysis of Time Complexity)' 입니다.

그럼 시작해보죠!

간단히 유도를 해보겠습니다. 우선, 이진 탐색을 반복할수록 남아있는 (탐색할) 자료의 개수가 어떻게 될까요?

처음에 입력된 갯수를 N 이라하면,

첫 시행 후에는 반이 버려져서