Binary Search Logic

Question

I was trying to do a binary search algorithm, but I faced myself with a logic problem and I don't understand why that doesn't work...

var binarySearch = function(list, num) {
  var low = 0, high = list.length - 1, mid = Math.floor((high - low) / 2);
  while(mid != num) {
    if(num > list[mid]) {
      low = mid;
      mid = Math.floor((high - low) / 2);
    } else {
      high = mid;
      mid = Math.floor((high - low) / 2);
    }
  }
  return mid;
}

var arr = [1, 3, 4, 5, 8, 10, 43, 55]
binarySearch(arr, 3);

This piece of code is returning 3 fine, but if I put a number like 43, it simply doesn't return anything...

Answer 1

Your main issues are:

1. Your condition in your while loop. mid is an index in your array, not an element. You can use list[mid] to get the element at your mid point.

2. You are setting low and hight to mid. But you don't need to re-check these (are you're already checking the mid position in your while loop). You can use mid+1 or mid-1 instead.

3. Your recalculation of the midpoint is not correct. You want to get the average between the high and low using Math.floor((high + low) / 2); instead (note the +).

4. Currently your while loop only stops once it finds a match. You need to also stop it once you've exhausted all possibilities. This can be done using an additional check to check that the low pointer hasn't passed the hight pointer.

5. You then need to return a -1 if you can't find the element. This can be done by checking if your low and high pointers.

var binarySearch = function(list, num) {
  var low = 0, high = list.length - 1, mid = Math.floor((high + low) / 2);
  while(list[mid] != num && low <= high) {
    if(num > list[mid]) {
      low = mid+1;
      mid = Math.floor((high + low) / 2);
    } else {
      high = mid-1;
      mid = Math.floor((high + low) / 2);
    }
  }
  
  return low <= mid ? mid : -1;
}

var arr = [1, 3, 4, 5, 8, 10, 43, 55]
console.log(binarySearch(arr, 55));

You can simplify your code a little, by performing the equality check in your while loop, and moving the calculation of the mid:

var binarySearch = function(list, num) {
  var low = 0, high = list.length - 1;
  while(low <= high) {
    var mid = Math.floor((high + low) / 2);
    if(list[mid] === num)
      return mid;
      
    if(num > list[mid])
      low = mid+1;
    else
      high = mid-1;
  }
  
  return -1;
}

var arr = [1, 3, 4, 5, 8, 10, 43, 55]
console.log(binarySearch(arr, 55));