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

 

흔히 for 문을 이용해 배열의 처음부터 끝까지 탐색하는 선형탐색은 O(n) 이라는 시간복잡도로 효율성이 떨어집니다.

이를 보완하는 탐색 알고리즘으로 대체되는 이분탐색 (Binary Search, 이진 탐색이라고도 합니다 )은 O(log N) 의

시간 복잡도를 가지고 있습니다.

 

https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/

 

 

주어진 범위의 절반씩 삭제하며 윈도우를 조절하며 찾아가는 기법으로

주어진 배열은 순서대로 정렬이 되있어야 사용할 수 있는 알고리즘입니다.

 

32를 찾는 순서는 아래와 같이 절반의 범위를 줄여가며 진행됩니다

 

 

 

/**
 * 정렬된 배열에서 특정 요소의 인덱스를 찾는 이진 탐색 함수
 * @param {Array} arr - 검색할 정렬된 배열
 * @param {*} elem - 찾고자 하는 요소
 * @returns {number} - 요소가 있는 인덱스 또는 찾지 못한 경우 -1
 */
function binarySearch(arr, elem) {
    // 검색 범위의 시작 인덱스
    let start = 0;
    // 검색 범위의 끝 인덱스
    let end = arr.length - 1;

    // 중간 지점 계산
    let middle = Math.floor((start + end) / 2);
    
    // 중간값이 찾는 값과 다르고, 검색 범위가 유효한 동안 반복
    while(arr[middle] !== elem && start <= end) {
        // 찾는 값이 중간값보다 작으면 왼쪽 부분 탐색
        if(elem < arr[middle]) end = middle - 1;
        // 찾는 값이 중간값보다 크면 오른쪽 부분 탐색
        else start = middle + 1;
        // 새로운 중간 지점 계산
        middle = Math.floor((start + end) / 2);
    }
    // 찾는 값을 발견하면 해당 인덱스 반환, 못 찾으면 -1 반환
    return arr[middle] === elem ? middle : -1;
}

binarySearch([2,5,6,9,13,15,28,30], 103)