为什么这种二进制搜索实现会使浏览器无响应？

Question

我已经在我的 chrome 控制台中尝试过二进制搜索。但是当我运行代码时，整个 chrome 都挂了，我不得不删除页面：

var arr = [1, 3, 5, 8];
var binary = function (arr, search) {

    var low = 0;
    var high = arr.length - 1;
    var mid = (high + low) / 2;
    while (low <= high) {

        if (search === arr[mid]) {

            return mid;
        } else if (search > arr[mid]) {
            low = mid + 1;

        } else {
            high = mid - 1;
        }

    }
    return -1;
};

console.log(binary(arr, 3));

Answer 1

问题出在这一行

var mid = (high + low) / 2;

因为 mid 是一个浮点值，所以 arr[mid] 总是 returns undefined。你可以确认一下，像这样

var arr = [1, 3, 5, 8];
console.log(arr[1.5]);
// undefined

解决方案

要解决此问题，您可以将其转换为整数，如下所示
```
var mid = parseInt((high + low) / 2, 10);
```

正如 Rick 在评论中指出的那样，mid 计算必须在 while 循环内进行。所以，while 循环看起来像这样

while (low <= high) {
    mid = parseInt((high + low) / 2, 10);
    if (search === arr[mid]) {
        return mid;
    } else if (search > arr[mid]) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}

Answer 2

在您的代码中，mid总是 1.5，因为它是在循环之前计算的。

相反，将 mid 计算 移动到 循环中，并将其计算为 high 和 low 的四舍五入平均值：

var arr = [1, 3, 5, 8];
var binary = function(arr, search) {

  var low = 0;
  var high = arr.length - 1;
  var mid;

  while (low <= high) {
    mid = Math.round((high + low) / 2);
    if (search === arr[mid]) {
      return mid;
    } else if (search > arr[mid]) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
};

console.log(binary(arr, 3)); //1
console.log(binary(arr, 8)); //3
console.log(binary(arr, 17)); //-1

为什么这种二进制搜索实现会使浏览器无响应？

Why does this binary search implementation make the browser unresponsive?

javascript

arrays

binary-search