[알고리즘 JS] 이분 탐색

반복문 구현

function binarySearchWithLoop(sortedArray, val) {
    let left = 0;
    let right = sortedArray.length - 1;
    let mid;
    
    while(left <= right) {
        mid = Math.floor((left+right) / 2);
        
        if(sortedArray[mid] == val) {
            return mid;
        } else if(sortedArray[mid] > val) {
            right = mid-1;
        } else {
            left = mid+1;
        }
    }
    
    return -1;
}

 

재귀 구현

function binarySearchWithRecursion(sortedArray, val) {
    let left = 0;
    let right = sortedArray.length - 1;
    
    if(left > right) return -1;
    
    let mid = Math.floor((left+right) / 2);
    
    if(sortedArray[mid] == val) {
        return mid;
    } else if(sortedArray[mid] > val) {
        binarySearchWithRecursion(sortedArray.slice(0, mid),val);
    } else {
        binarySearchWithRecursion(sortedArray.slice(mid+1),val);
    }
    
    return -1;
}