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

Question

对于二分查找问题，我想出了以下解决方案：

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

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

Answer 1

是的，第二种方案更好。它是唯一一个实际执行二进制搜索的（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);

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

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 的数组，您从 left 0 和 right 99 开始，然后在循环内的每次迭代中，您向左递增 1 或向右递减 1。真正的二进制搜索将涉及递增或递减以将要搜索的剩余元素减少大约一半 - 例如，从 0-99 开始，然后转到 0-49，然后是 24-49，然后是 24 -36，依此类推。这样你到达目标（如果它存在）比 0-99，然后 0-98，然后 0-97 等快得多

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

alternative solution to binary search just as good?

javascript

algorithm

search

binary-search