Почему эта реализация бинарного поиска делает браузер невосприимчивым?

Question

Я пробовал двоичный поиск в моей хром-консоли. Но когда я побежал код, весь хром был повешен, и я должен был убить страницы:

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

В вашем коде, 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

Answer 2

Проблема заключается в этой строке

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. Как отметил Рик в комментариях, расчет 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; 
       } 
   }