While working on a simple binary search algorithm, I encountered an issue where using mid-- gave different results compared to mid -= 1 or mid - 1, ultimately causing the function to fail. After researching online and reading various Stack Overflow posts, it appears that the -- and ++ operators can impact the value of mid for each iteration. However, the exact behavior behind these operators seems quite nuanced and difficult to track. Any assistance on this matter would be greatly appreciated.
My understanding is that both mid -= 1 and mid-- are intended to decrease the value of mid by one, effectively assigning the new value of mid as -1.
Correct Implementation
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
// []
Incorrect Implementation
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
// []
// []
// []