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