코딩테스트를 위한 이분탐색

프론트엔드 개발자는 가끔 자바스크립트로 문제를 풀어야한다. 하지만, 애처롭게도 c++에는 내장 라이브러리로 존재하는 binary_search, lower_bound, upper_bound가 존재하지 않느다. 따라서, 우리는 이분탐색을 "직접" 만들어야한다. 이분탐색에 대해 알아보자

 

Binary Search

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;
}

 

Lower Bound

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

    while(left < right){
        let mid = Math.floor((left+right)/2);

        if(arr[mid] < target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
}

• lower bound 는 배열에서 타겟값 이상이 처음으로 나타나는 위치를 찾는다.
• 이분탐색 하다가 target 값 이상인 left 값이 타겟값을 넘는 첫 위치다.

Upper  Bound

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

    while(left < right){
        let mid = Math.floor((left+right)/2);

        if(arr[mid] <= target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
}

• upper bound 는 배열에서 타겟값보다 큰 값이 나타나는 첫 위치를 찾는다.
• 타겟값을 초과하는 인덱스를 반환한다.

이분탐색 vs lower, upper

• 이분탐색은 탐색값을 찾는것 이므로 while의 조건이 left<=right다.
• lower, upper 는 탐색값의 바운더리를 찾는 것 이므로 while의 조건이 left < right다.