Why does this binary search implementation make the browser unresponsive?

Question

I've tried binary search in my chrome console. But when I've ran the code, the whole chrome got hanged and I had to kill the pages:

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

In your code, mid is always 1.5, because it's calculated before the loop.

Instead, move the mid calculation within the loop, and calculate it as the rounded average of high and 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

The problem is in this line

var mid = (high + low) / 2;

Since mid is a floating point value, arr[mid] always returns undefined. You can confirm this, like this

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

Solution

1. To fix this, you can convert that to an integer, like this

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

2. As pointed out by Rick in the comments, the mid calculation has to happen within the while loop. So, the while loop would look like this

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