이진 탐색 - 간단하고 강력한 탐색 알고리즘 ( 2 )

이번 포스트에서는 드디어 이진 탐색 알고리즘에 대해서 알아보도록 하겠습니다.
유의해야 할 점은 항상 배열에 대한 정렬이 선행되어야 한다는 점입니다.
그럼 시작하겠습니다.

---

1. 이진 탐색 ( Binary Search ) 이란?

 이진 탐색이란 오름차순으로 정렬된 배열에 대하여 단계를 거치며 검색의 범위를 점차 줄여나가 최종적으로 찾고자 하는 값의 위치를 찾는 알고리즘입니다.    

이렇게만 써놓고 보면 이해하기 힘듭니다.

예시로 알아보겠습니다.

우리는 '7' 이라는 숫자를 찾아보도록 하겠습니다.

배열은 역시 오름차순으로 정렬된 배열입니다.

 

• 1 단계 : 배열의 길이를 2로 나누어 가운데 인덱스에 위치한 원소의 값을 확인합니다.

 

9가 나왔네요

 

• 2 단계 : '9' 라는 값이 나왔는데 우리가 찾고자 하는 값인 '7'은 오름차순인 배열 안에서 '9' 보다 왼쪽에 위치해 있습니다. 때문에 왼쪽의 남은 배열을 2로 다시 나누어 줍니다. 나눈 결과 값이 짝수이기에 가운데 위치한 인덱스가 두 개 나오는데 양쪽 인덱스 중 임의로 선택하여 값을 확인합니다.

 

4가 나왔네요

 

• 3 단계 : '4'라는 값은 '7' 보다 작기에 우리가 찾는 값은 남은 배열의 오른쪽에 위치해 있을 것입니다.  남은 배열이 두 부분 남았으므로 임의의 인덱스를 다시 선택합니다.

 

 

2. 이진 탐색의 시간 복잡도

위의 예에서는 총 3단계에 걸쳐서 우리가 원하는 값인 '7'을 찾았습니다. 만일 선형 탐색으로 탐색을 하였다면 몇 단계였을까요? 맞습니다. 이진 탐색과 동일한 총 3단계에 걸쳐 탐색 했을 것입니다. 하지만 탐색해야 하는 배열의 크기가 커지면 어떻게 될까요?

 

•   크기가 100인 배열 - 선형 탐색 : 100단계 , 이진 탐색 : 7단계
•   크기가 200인 배열 - 선형 탐색 : 200단계 , 이진 탐색 : 8단계
•   크기가 400인 배열 - 선형 탐색 : 400단계 , 이진 탐색 : 9단계
•   크기가 800인 배열 - 선형 탐색 : 800단계 , 이진 탐색 : 10단계

 

혹시 패턴이 보이시나요?

배열의 크기가 2배 늘어날 때마다 선형 탐색의 단계가 원소 수만큼 늘어난다면 이진 검색은 단 1단계가 늘어납니다.

이게 바로 정렬된 배열과 이진 탐색의 놀라운 힘입니다.

원소의 개수가 2배 늘어날 때마다 연산 단계가 1 증가하므로 시간 복잡도는 $O(log_2N)$라 할 수 있겠습니다.

 

3. 이진 탐색의 코드 구현

이제 실사용을 위해서 코드로 구현해 보겠습니다.

function binarySearch(array, searchValue) {
    // 탐색할 배열의 크기를 제한해 줄 상한선과 하한선
    let lowerBound = 0;
    let upperBound = array.length - 1;
    // 탐색하여 값을 확인해볼 위치
    let midPoint;
    // 상한선과 하한선이 같아질 때까지 반복
    while (lowerBound <= upperBound) {
    	// 중간값이 소숫점이 나오지 않도록 항상 올림연산
        midPoint = Math.ceil((lowerBound + upperBound) / 2);
        let midValue = array[midPoint];
        if (searchValue !== midValue) {
        	// 중간값이 찾는값보다 크다면 오른쪽 배열 제외
            if (searchValue < midValue) {
                upperBound = midPoint - 1;
            // 중간값이 찾는값보다 작다면 왼쪽 배열 제외
            } else if (searchValue > midValue) {
                lowerBound = midPoint + 1;
            }
        } else {
            return midPoint;
        }
    }
    return null;
}

마치며

이번 포스트에서는 이진검색을 알아봤습니다.
사실 전 이번 글을 포스팅하면서 제가 알고리즘을 공부하기 전인 대학생 때 술자리에서 즐기던 "Up-Down"이라는 게임이 떠오르며 즐거웠습니다. 혹시 여러분도 이러한 경험이 떠오르셨나요?
이상으로 이번 포스트를 마치겠습니다. 감사합니다.

 

관련글

이진 탐색 - 간단하고 강력한 탐색 알고리즘 ( 1 )