时间戳

首页 > 解决方案 > 二进制搜索的替代解决方案同样好？

javascript - 二进制搜索的替代解决方案同样好？

问题描述

对于二进制搜索问题，我提出了以下解决方案：

function binarySearch(arr,numba){
    
    var left = 0
    var right = arr.length - 1
    
    while (left <= right){
        let middle = Math.floor((left+right)/2)
        if (arr[middle] < numba){
            left ++;
            
        }
        else if (numba < arr[middle]){
            right -- ;
            
        }
        else if (numba === arr[middle]){
            return middle
        }
    }
    return -1
}

但建议的解决方案是：

function binarySearc(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var 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);
    }
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}

第二种解决方案是否比我所拥有的更好，或者它们本质上是一样的？

标签： javascriptalgorithmsearchbinary-search

解决方案

是的，第二种解决方案更好。它是唯一实际执行二分搜索的（计算复杂度为O(log n)）。middle请参阅下面的代码片段，了解使用建议的解决方案需要重新计算多少次：

function binarySearc(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    let iterCount = 0;
    while(arr[middle] !== elem && start <= end) {
        iterCount++;
        if(elem < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    console.log('iterCount', iterCount);
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}

const arr = Array.from({ length: 100 }, (_, i) => i);
binarySearc(arr, 30);

相反，您的解决方案需要按时间middle顺序重新分配O(n)- 它实际上并没有进行二进制搜索。

function binarySearch(arr,numba){
    
    var left = 0
    var right = arr.length - 1
    
    let iterCount = 0;
    while (left <= right){
        iterCount++;
        let middle = Math.floor((left+right)/2)
        console.log(middle);
        if (arr[middle] < numba){
            left ++;
            
        }
        else if (numba < arr[middle]){
            right -- ;
            
        }
        else if (numba === arr[middle]){
            console.log('iterCount', iterCount);
            return middle
        }
    }
    return -1
}

const arr = Array.from({ length: 100 }, (_, i) => i);
binarySearch(arr, 30);

例如，对于长度为 100 的数组，您从left0 和right99 开始，然后在循环内的每次迭代中，您要么向左递增 1，要么向右递减 1。真正的二分搜索将涉及递增或递减到 cut将剩余的元素向下搜索大约一半 - 例如，从 0-99 开始，然后转到 0-49，然后是 24-49，然后是 24-36，依此类推。这样你就可以比 0-99、0-98、0-97 等更快地到达目标（如果存在）。

推荐阅读