이분 탐색(Binary Search)

(오름차순으로)정렬된 배열에서 범위를 절반으로 좁히며 원하는 값의 위치를 탐색하는 알고리즘

• 탐색의 범위를 정하는데 시작점, 끝점, 중간점을 이용합니다.
• 탐색 절차
  
  • 배열의 중간점에 위치한 값을 찾아야하는 데이터와 비교합니다.
  • 값이 더 크다면 중간값 왼쪽의 배열로 범위를 좁히고 탐색을 반복합니다.
  • 값이 더 작다면 중간값 오른쪽의 배열로 범위를 좁히고 탐색을 반복합니다.

시간복잡도

• O(logn)
  • 매번 비교 연산의 대상이 절반으로 줄어갑니다.
  • 따라서 비교 연산의 횟수는 배열의 갯수가 n일 때 log₂n입니다.

공간복잡도

• O(logn)
  • 재귀로 구현할 경우 재귀 함수의 호출 횟수에 비례
• O(1)
  • 반복문으로 구현할 경우, 같은 변수를 재활용하기 때문에 O(1)

구현

재귀

let binarySearch = function (array, start, end, target) {
    // 배열 길이가 0이면 탐색 실패
    if (start > end) {
        return null
    }
    let middle = Math.floor((start + end) / 2);
    // 타겟과 같으면 middle 반환
    if (array[middle] === target) {
        return middle;
    }
    // 타겟보다 가운데 값이 작으면 오른쪽 배열 탐색
    if (array[middle] < target) {
        return binarySearch(array, middle + 1, end, target);
    } else { // 타겟보다 가운데 값이 크면 왼쪽 배열 탐색
        return binarySearch(array, start, middle - 1, target);
    }
}

let sample = [1, 3, 4, 5, 6, 9, 11, 13, 15, 17, 18]
let target = 17;
let result = binarySearch(sample, 0, sample.length - 1, target);
if (result) {
    console.log(`${target}은 ${result + 1}번째에 있습니다.`)
} else {
    console.log(`${target}은 배열에 없습니다.`)
}
/* 탐색 결과 출력
17은 10번째에 있습니다.
*/

 

반복

let binarySearch = function (array, target) {
    let start = 0;
    let end = array.length - 1;
    while (start < end) {
        // 중간값은 인덱스로 사용하기 때문에 소수점 제거
        let middle = Math.floor((start + end) / 2);
        // 타겟과 같을 경우 middle 반환
        if (array[middle] === target) {
            return middle;
        }
        // 타겟보다 작은 경우는 시작값을 중간값+1로 교체 후 반복
        if (array[middle] < target) {
            start = middle + 1;
        } else { // 타겟보다 큰 경우는 종료값을 중간값-1로 교체 후 반복
            end = middle - 1;
        }
    }
    return null
}
let sample = [1, 3, 4, 5, 6, 9, 11, 13, 15, 17, 18]
let target = 17;
let result = binarySearch(sample, target);
if (result) {
    console.log(`${target}은 ${result + 1}번째에 있습니다.`)
} else {
    console.log(`${target}은 배열에 없습니다.`)
}
/* 탐색 결과 출력
17은 10번째에 있습니다.
*/