이진탐색(Binary Search)

이진탐색은 데이터를 반으로 나눠가면서 데이터를 찾는 방식을 뜻한다.

이진탐색은 특성상 데이터가 정렬된 상태여야 한다. 데이터가 정렬된 상태라면 아래의 순서로 진행한다.

 

1단계: 전체 배열의 중간 인덱스의 원소와 검색값을 비교한다.

2단계: 검색값이 배열의 좌우 중 한 곳에 포함되면 다시 1단계를 반복한다.

 

즉, 중간을 자르고 크기를 비교하는 것을 반복하는 것이 이진탐색 알고리즘이며, 선형탐색보다 검색 횟수가 적기 때문에 시간 복잡도에서 우위가 있다.

   
// 중앙 값을 구해서 나머지를 버린다.(이 때문에 mid가 left값과 더 가까울 수 있음)
// 배열에서 mid인덱스 값이 타겟값인 경우 리턴한다.
// mid인덱스 값이 타겟보다 작으면 mid에 1을 더한 값을 left에 할당한다. 새로 만들 mid값을 오른쪽으로 당기기 위해서다.
// 큰 경우 mid -1 한 값을 right에 할당한다. 새로 만들 mid값을 왼쪽으로 당기기 위해서다.
// 위 과정을 반복하면 하나의 값에 수렴하게 되고, 이것이 mid, 즉 target값이 되면서 반환된다.

function binarySearch(arr, target) {

    let left = 0;
    let right = arr.length - 1;

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

console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 7));
// 6 (배열의 6번째 인덱스)

 

이진탐색은 O(log n)의 시간 복잡도를 가진다. 중간값을 취하는 방식은 탐색 시간을 로그 선형적으로 감소시킨다. 이진 탐색을 자바스크립트로 구현할 때 재귀적 형태를 만들어 코드를 구현하기도 한다. 그러면 추가적인 공간 복잡도를 발생시키므로 O(n)의 공간 복잡도를 만들 수 있다. 위와 같이 추가 메모리를 차지하지 않는 형태로 작성해야 O(1)의 공간 복잡도를 가질 수 있다.

 

예제1)

/*
    서점으 ㅣ모든 책이 부된 ISBN 번호대로 정렬돼 있다고 가정.
    책을 찾는 함수를 작성하시오.
*/
let bookISBNs = [9788998139019, 9788998139020, 9788998139021, 9788998139023];

const binarySearch = (arr, target) => {
    let left = 0;
    let right = arr.length - 1;

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



console.log(binarySearch(bookISBNs, 9788998139020));
// 1

console.log(binarySearch(bookISBNs, 9788998139021));
// 2

console.log(binarySearch(bookISBNs, 9788998139023));
// 3

 

 

예제2)

/*
    향기로운 학교 만들기

    복도에는 여러 교실이 있고 교실의 간격은 다르다.
    배치할 수 있는 꽃나무도 여러 개 있다.
    인접한 꽃나무끼리의 거리를 최대한 멀리하여 여러 교실에 향이 닿게 하고자 한다.
    - 복도는 x축이라고 보고 교실의 위치는 x좌표 위에 있는 점으로 가정한다.
    - 출력값은 꽃나무를 배치할 위치를 배열로 반환한다.
*/

let CLASSROOMS = [4, 7, 2, 5, 10, 13];
let FLOWER_TREES = 3;

// 이진탐색 전 정렬
CLASSROOMS.sort((a,b) => a - b);

let start = CLASSROOMS[0];
let end = CLASSROOMS[CLASSROOMS.length - 1];

let result = 0;

while (start <= end) {
    let mid = Math.floor(( start + end ) / 2);
    let value = CLASSROOMS[0]
    let count = 1;

    for(let i = 1; i < CLASSROOMS.length; i++) {
        if(CLASSROOMS[i] - value >= mid) {
            value = CLASSROOMS[i];
            count++
        }
    }

    if(count >= FLOWER_TREES) {
        result = mid;
        start = mid + 1;
    } else {
        end = mid - 1;
    }
}

let treePositions = [CLASSROOMS[0]];
let lastPosition = CLASSROOMS[0];

for(let i = 1; i < CLASSROOMS.length; i++) {
    if( CLASSROOMS[i] - lastPosition >= result) {
        treePositions.push(CLASSROOMS[i]);
        lastPosition = CLASSROOMS[i];
    }
}

console.log(treePositions);

// [ 2, 7, 13 ]