[알고리즘] 이진 탐색 ( Binary Search )

포스팅 목적

효율적인 탐색 알고리즘 중 하나인 이진 탐색을 코드 구현을 중심으로 알아봅니다.

 

이진 탐색의 정의

이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다.

예를 들어 특정 범위에 있는 숫자를 맞추는 UP & DOWN 게임을 할 때를 생각해 보면 가장 안정적이고 빠르게 답을 찾는 방법은 가장 한 숫자 범위 내에 있는 수 중에서 중간에 있는 숫자를 찍어서 그 숫자보다 큰지 작은지에 따라 다음 숫자를 결정하는 것 입니다. 이것이 이진 탐색입니다.

 

이진 탐색의 장단점

이진 탐색의 장점은 높은 효율성 입니다. 한 번 탐색할때 마다 탐색의 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log N) 입니다. 

앞의 정의에 나왔듯이 이진 탐색은 정렬되어 있는 배열에서만 사용할 수 있기 때문에 이진 탐색의 단점은 정렬이 되지 않는 배열은 정렬을 하고 사용해야 한다는 것입니다. 그런데 정렬 알고리즘은 오히려 시간 복잡도가 O(N log N) ~ O(N^2) 정도이기 때문에 효율적이지 못한 동작을 하게 됩니다.

 

예시 코드

const findTargetIdx = function(nums, target){
    let  left = nums[1];
    let right = nums[nums.length - 1];

    while(left <= right){    	
        const mid = Math.floor((left + right) / 2);

        if(target < nums[mid]){
            right = mid - 1;
        } else if(nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

const nums = [...Array(17).keys()]; // 정렬된 자료
const target = 6;

console.log(findTargetIdx(nums, target));

target 이 nums[mid] 보다 작으면 왼쪽으로 옮기고, 크면 오른쪽으로 옮기고, 일치하면 반환하는 단순하면서도 직관적으로 구현된 코드입니다.

 

+) 연습 코드

const findTargetIdx1 = function(nums, target){
    let  left = nums[1];               // 초기   왼쪽 끝 인덱스
    let right = nums[nums.length - 1]; // 초기 오른쪽 끝 인덱스

    // left <= right 조건일 경우 무한 루프
    // CASE : 6 6 6
    while(left < right){
    	// Math.ceil 할 경우 무한 루프
        // CASE : 6 7 7 -> 6 7 7
        const mid = Math.floor((left + right) / 2);
        console.log(`nums[${left}]:${nums[left]} / nums[${mid}]:${nums[mid]} / nums[${right}]:${nums[right]}`);
		
        // target < nums[mid] 조건일 경우 오답
        // CASE : 5 6 8 -> 7 7 8
        if(target <= nums[mid]){
            // target 일 경우
            // mid 를 왼쪽으로 이동시켜야할 조건
            right = mid;
        } else {
            // mid 를 오른쪽으로 이동시켜야할 조건
            left = mid + 1;
        }
    }

    console.log(`left:${left} / right:${right}`);
    return left; // 종료 될 때의 index 는 left 와 right 가 같음
}

const findTargetIdx2 = function(nums, target){
    let  left = nums[1];
    let right = nums[nums.length - 1];

    while(left < right){    	
        const mid = Math.ceil((left + right) / 2);
        if(target < nums[mid]){
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    return left;
}

• #33. Search in Rotated Sorted Array
• #153. Find Minimum in Rotated Sorted Array

직관적으로 이해되는 위쪽의 예제와 다르게 Leet Code 에서 이 2문제를 풀다가 등호 조건이나 right = mid 로 하는 이유 등이 헷갈려서 연습삼아 만든 코드입니다. Leet Code 의 Discuss 탭에 많은 사람들이 저렇게 구현을 했는데 아마도 소스가 더 짧아서 그렇게 한 것 같습니다. 

 

참고 자료

• 이진 탐색과 시간 복잡도 분석
• [알고리즘] Binary Search 이진 탐색 : 필수 기본 정리 - 장점, Kotlin 구현