이진(이분) 탐색

1. 이진(이분) 탐색

이진 탐색이란 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 정렬되어 있는 리스트에서 찾으려는 데이터와 중간 위치의 데이터를 비교하며 탐색 범위를 절반씩 좁혀거며 데이터를 찾는 방법으로, 배열 데이터가 정렬되어 있어여만 사용할 수 있는 알고리즘이다.

 

시간 복잡도는 아래와 같다.

전체 데이터의 수를 N이라고 가정했을 때

1) 첫 번째 탐색 후 절반만 남아 남은 수가 \( \frac{N}{2} \) 개

2) 두 번째 탐색에서 다시 절반만 남아 남은 수가 \( \frac{N}{2} \) * \( \frac{1}{2} \) 개

3) 세 번째 탐색에서 다시 절반이 남아 남은 수가 \( \frac{N}{2} \) * \( \frac{1}{2} \) * \( \frac{1}{2} \) 개

.....

k) 규칙을 찾아보면 k번째 탐색에서 남은 데이터 수는 \( (\frac{1}{2})^k \) * N 이 된다. 

 

위와 같은 탐색을 반복하다보면 탐색이 끝나는 시점에는 (최악의 경우는 찾는 데이터가 없는 경우) 남은 자료가 1개이다.

따라서 최악의 경우 \( (\frac{1}{2})^k \) * N =1 이 된다. 

위 식의 양변에 \( 2^k \) 를 곱하면 \( 2^k=N \)이 되고 다시 양변에 log2 를 곱하면 최종 식은 k= log2 * N 이 된다.
따라서 시간복잡도는 O(log2N) 으로 나타 낼 수 있다.

 

Ex) 백준 1920번 : 수 찾기

1920번: 수 찾기

 

* 구현

1. [4, 1, 5, 2, 3] => [1, 2, 3, 4, 5] 로 정렬
2. [1, 3, 7, 9, 5] 배열을 순환하며 1번 배열에 값이 있는지 없는지 이분탐색을 진행

function solution(input) {
    let result = [];
    let originArr = input[1].split(' ').map((dr) => Number(dr)).sort((a, b) => a - b);
    let findArr = input[3].split(' ').map((dr) => Number(dr));

    let strIdx = 0; // 재귀에서 사용
    let endIdx = originArr.length - 1; // 재귀에서 사용
    
    findArr.forEach((dr) => {
    
        result.push(binarySearch(originArr, dr)); // 1.비 재귀 시
        
        result.push(binarySearch(originArr, strIdx, endIdx, dr)); // 2.재귀 시
        
    });

    console.log(result.join('\n'))
}

// 1.이분 탐색 비 재귀
function binarySearch(originArr, findValue) {
    let sIdx = 0; // 시작 인덱스 
    let eIdx = originArr.length - 1; // 종료 인덱스 
    let mid = Math.floor((sIdx + eIdx) / 2); // 중간 값
    
    while (eIdx - sIdx >= 0) { //종료 인덱스가 시작 인덱스보다 클때까지만 반복
    
        // 탐색값과 같으면 종료
        if (originArr[mid] == findValue) {
            return 1
        }
        // 탐색값이 크면 중간 기준 왼쪽으로
        else if (originArr[mid] > findValue) {
            eIdx = mid - 1;
        }
        // 탐색값이 작으면 중간 기준 오른쪽으로
        else {
            sIdx = mid + 1;
        }
        
        // 탐색값과 다를 경우 중간값을 다시 설정
        mid = Math.floor((sIdx + eIdx) / 2);
    }

    return 0
}

// 2.이분 탐색 재귀
function binarySearch(arr, sIdx, eIdx, findValue) {
    let mid = Math.floor((sIdx + eIdx) / 2);

    if (eIdx - sIdx >= 0) {
        if (arr[mid] == findValue) {
            return 1
        } else if (arr[mid] > findValue) {
            return binarySearch(arr, sIdx, mid - 1, findValue);
        } else {
            return binarySearch(arr, mid + 1, eIdx, findValue);
        }
    }

    return 0
}

 

 

*참고

[Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도