Why does this binary search implementation make the browser unresponsive?

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

Answers:

Answer

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

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

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.