在 javascript 中使用 for 循环进行二进制搜索

Question

我正在尝试在 javascript 中使用 for 循环实现二进制搜索，但它在一些测试用例中失败了，下面是我的代码

function binarySearch(arr, val){
    let start = 0
    let end = arr.length - 1
    let middle = Math.floor((start + end)/2)

    for(let i = start; i<= end; i++){
        if(val === arr[middle]) { 
           return middle
        }

        if(val < arr[middle]){
            end = middle - 1
        }

        if(val > arr[middle]){
           start = middle + 1
        }

        middle = Math.floor((start + end)/2)
    }
        return -1
  }

    // test case:1 console.log(binarySearch([5, 6, 9, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 9))
    
    
   // test case:2 console.log(binarySearch([1,3,4,5,6,7,8,9, 10], 10))

它通过了第二个测试用例，但在第一个测试用例中惨遭失败。任何人都可以提出一些建议吗？

Answer 1

我意识到为什么在这种情况下不使用“for 循环”。

这是因为在循环中我为“start”分配了一个新值，但是当您发现“i”的值保持与之前初始化的“start”值相同的事实时，问题就出现了。

同样的情况发生在 i <= end

我的意思是“i”除了 i++ 之外没有被重新分配任何东西。我已经意识到，在这些情况下，最好使用 while 循环迭代而不是 for 循环，因为您需要从循环内部重新初始化索引。

Answer 2

就像你说的 Nishant，While 循环适合这种情况，因为你应该在循环内更新左（开始）、右（结束）和中间索引的值。

二进制搜索的迭代实现（在 Java 中）：

public int binarySearch(int[] array, int target) {
    var left = 0;
    var right = array.length - 1;

    while (left <= right) { 
        var middle = (left + right) / 2;

        if (array[middle] == target)
            return middle;

        if (target < array[middle]) 
            right = middle - 1;
        else
            left = middle + 1;
    }

    return -1;
}

在 javascript 中使用 for 循环进行二进制搜索

binary search using for loop in javascript

javascript

algorithm

binary-search

data-structures