increments returning different binary search result-CodePudding

Created a simple binary search and I noticed that the usage of mid-- vs mid -= 1 or mid - 1 returned different results and essentially caused the function to fail. I was scanning resources online and based on reading other SO posts, my assumption is that the -- and operators are able to change the value of mid for each iteration ... but it seems so nuanced that I'm not really tracking what's going on behind the scenes. Would appreciate some help regarding this.

I would think that both mid -= 1 and mid-- mean take mid and reduce its value by one. Both essentially reassigning the -1 value to the mid variable.

works

const sourceArray = [1, 5, 7, 10, 15];

const binarySearch = (array, target) => {
  let low = 0;
  let high = array.length - 1;

  while (low < high) {
    let mid = (low   high) / 2;
    if (array[mid] === target) {
      return mid;
    } else if (array[mid] > target) {
      // if array[mid] > target, set high to mid--
      high = mid--;
    } else {
      // if array[mid] < target, set low to mid  
      low = mid  ;
    }
  }
  return [];
};

console.log(binarySearch(sourceArray, 7));
console.log(binarySearch(sourceArray, 10));
console.log(binarySearch(sourceArray, 15));
console.log(binarySearch(sourceArray, 20));

// returns
// 2
// 3
// 4
// []

doesnt work

const sourceArray = [1, 5, 7, 10, 15];

const binarySearch = (array, target) => {
  let low = 0;
  let high = array.length - 1;

  while (low < high) {
    let mid = (low   high) / 2;
    if (array[mid] === target) {
      return mid;
    } else if (array[mid] > target) {
      // if array[mid] > target, set high to mid--
      high = mid -= 1;
    } else {
      // if array[mid] < target, set low to mid  
      low = mid  = 1;
    }
  }
  return [];
};

console.log(binarySearch(sourceArray, 7));
console.log(binarySearch(sourceArray, 10));
console.log(binarySearch(sourceArray, 15));
console.log(binarySearch(sourceArray, 20));

// returns
// 2
// []
// []
// []

CodePudding user response：

The post-decrement operator (--) returns the value, then decrements it, so if mid is 3, your line:

high = mid--;

Sets high to 3 and then decrements mid by 1, leaving 2 in mid.

In your second example, you have two assignments on the same line:

high = mid -= 1;

Let's use the example of mid with a value of 3 again. Multiple assignments in a single statement work right-to-left. First, you are subtracting 1 from mid and storing the value 2 in mid. Then, you are assigning that 2 to high.

CodePudding user response：

Firstly, the while condition should be low <= high. Consider having an array of a single element, that won't enter the loop at all.

Secondly, you should use Math.floor((low high) / 2); instead. Consider low and high having a different parity. Clearly, mid will be a fractional value. For example, you will access sourceArray[2.5] which is undefined.

Finally, you should use the prefix increment and decrement because they return their value after incrementing and decrementing i.e --mid and mid

The modifications I made in your code:

const sourceArray = [1, 5, 7, 10, 15];

const binarySearch = (array, target) => {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    let mid = Math.floor((low   high) / 2);
    if (array[mid] === target) {
      return mid;
    } else if (array[mid] > target) {
      // if array[mid] > target, set high to mid - 1
      high = --mid;
    } else {
      // if array[mid] < target, set low to mid   1
      low =   mid;
    }
  }
  return [];
};

console.log(binarySearch(sourceArray, 7));
console.log(binarySearch(sourceArray, 10));
console.log(binarySearch(sourceArray, 15));
console.log(binarySearch(sourceArray, 20));