算法基础 - 二分法

二分法，目的是找到目标对象的索引值，取中位数和数组的中间元素比较，如果等于中间元素，则直接返回。如果不等于则取半继续查找

实现

下面的实现，默认给出的数组是从小到大依次排序的

递归实现

function binarySearch({arr,target,startIndex,endIndex}){
    // 如果数组的最大值小于目标值，直接返回 -1
    if( arr[endIndex] < target ) return -1;
    const midIndex = Math.floor((endIndex + startIndex)/2);
    // 如果中位数和目标值相等，直接返回
    if( arr[midIndex] === target ){
        return midIndex;
    }else{
        // 如果中位数小于目标值，则取右侧数据
        if( arr[midIndex] < target ){
            return binarySearch({
                arr,
                target,
                startIndex: midIndex + 1,
                endIndex
            });
        } else {
            return binarySearch({
                arr,
                target,
                startIndex,
                endIndex: midIndex - 1
            });
        }
    } 
}

测试用例

const testArray = [2,4,7,11,12,14,16,30,32,33,35,40,42,45];

function binarySearch({arr,target,startIndex,endIndex}){
    // 如果数组的最大值小于目标值，直接返回 -1
    if( arr[endIndex] < target ) return -1;
    const midIndex = Math.floor((endIndex + startIndex)/2);
    // 如果中位数和目标值相等，直接返回
    if( arr[midIndex] === target ){
        return midIndex;
    }else{
        // 如果中位数小于目标值，则取右侧数据
        if( arr[midIndex] < target ){
            return binarySearch({
                arr,
                target,
                startIndex: midIndex + 1,
                endIndex
            });
        } else {
            return binarySearch({
                arr,
                target,
                startIndex,
                endIndex: midIndex - 1
            });
        }
    } 
}

const index = binarySearch({
    arr: testArray,
    target: 40,
    startIndex: 0,
    endIndex: testArray.length-1
})

console.log(index)