[Algorithm] 이진 검색(Binary Search)을 이용한 알고리즘 풀이

* Case

리트코드에서 다음과 같은 알고리즘 문제를 풀게 되었다. 

35. Search Insert Position 
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

오름차순으로 정렬된 배열과 타겟값이 주어진다. 배열 내에서 타겟값과 동일한 요소의 인덱스를 찾아야 한다. 타겟값과 일치하는 요소가 없는 경우에는 정렬 순서에 맞추어 타겟값을 배열 안에 넣을 때, 타겟값의 인덱스를 구하는 문제다.

단순하게 생각해본다면 배열에 반복문을 사용해 앞에서부터 값을 타겟과 비교해보면 될 것이다. 이를 코드로 구현해보면 다음과 같다. 

var searchInsert = function(nums, target) {
// 반복문을 사용해 배열 내 요소와 타겟값과의 크기를 비교한다. 
    for(let i = 0; i < nums.length; i++){
    // 타겟이 배열의 첫 요소보다 작으면 타겟은 배열의 맨 앞에 위치해야 하므로 0 리턴
        if(nums[0] > target){
            return 0
        };
        // 요소와 타겟값이 같으면 해당 인덱스를 리턴한다
        if(nums[i] === target){
            return i;
        }
	// 타겟값이 i번째와 i+1 번째 요소값 사이에 있다면 i+1 을 리턴
        if(nums[i] < target && nums[i + 1] > target){
            return i + 1;
        }
	// 타겟이 배열 내 마지막 요소보다 클 경우 배열의 맨 뒤에 위치해야 하므로 배열의 길이 리턴
        if(nums[nums.length - 1]  < target){
            return nums.length;
        }
    }
};

위 방법을 사용하면 원하는 값을 찾아낼 수 있다. 이 경우, 최대 배열의 개수만큼 연산이 이루어지므로 시간복잡도는 O(N)이 된다. 시간복잡도를 줄일 수 있는 다른 방법은 없을까?

 

* 이진 검색(Binary Search)을 사용한 풀이법

이진 검색을 사용하면 시간복잡도를 줄일 수 있다. 먼저 이진 검색에 대해서 위키백과는 다음과 같이 설명하고 있다.

이진 검색 알고리즘(Binary Search Algorithm)
이진 검색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 

 

오름차순으로 정렬된 배열의 중간값과 타겟 값을 비교해서 중간값이 크면 전체를 훑을 필요 없이 배열의 처음부터 중간값 이전까지에서만 타겟을 확인하면 된다. 반대로, 타겟값이 크면 중간값 + 1 부터 배열의 마지막까지 범위에서만 타겟값을 찾으면 된다. 

이진검색을 이용해 효과적으로 솔루션을 찾아낸 케이스가 있어 이를 아래와 같이 정리해보았다. 

var searchInsert = function(nums, target) {
// 재귀를 이용해 이진검색 정의
    function binarySearch(nums, target, start, end){
	// 타겟값이 배열 내 최대요소보다 크거나 최소요소보다 작은 경우    
        if (start > end) return start;
	// 배열 내 중간 인덱스 정의
        const midPoint = Math.floor((start + end) / 2);
	// 타겟값이 중간값과 동일하면 중간 인덱스 리턴
        if(nums[midPoint] === target) return midPoint;
	// 타겟값이 중간값보다 작으면 배열의 첫 요소부터 중간인덱스 - 1 범위에서 이진검색
	// 타겟값이 중간값보다 크면 중간인덱스 + 1부터 배열의 마지막 요소 범위에서 이진검색
        if(nums[midPoint] > target) return binarySearch(nums, target, start, midPoint - 1);
        if(nums[midPoint] < target) return binarySearch(nums, target, midPoint + 1, end);
    }
    위에서 정의한 이진검색 함수를 이용해 결과값 리턴
    return binarySearch(nums, target, 0, nums.length - 1);
};

 

위 경우에서는 이진 검색을 반복할수록 검색 범위가 2/N으로 줄어든다는 점을 확인할 수 있다. 즉 시간복잡도를 계산하면 O(log n)이 되어 기존 방법보다 훨씬 효율적이라는 점을 확인할 수 있다. 

정렬된 배열에서 특정 값을 찾는 경우, 이진검색을 활용한 알고리즘을 사용해보는 습관을 들이면 좋을 것 같다.