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

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] 总是返回 undefined。你可以确认这一点，像这样

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

解决方案

1. 要解决此问题，您可以将其转换为整数，如下所示

   var mid = parseInt((high + low) / 2, 10);
   

2. 正如 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;
       }
   }