While condition in my binary search algorithim in an Array

Viewed 56
var binarySearch = function (array, target) {
   if (array.length === 0) {
       return null;
   }
   
   if (array.length === 1) {
       if (array[0] === target) {
           return 0;
       } else {
           return null;
       }
   }
   
   let startIndex = 0;
   let endIndex = array.length - 1;

   while (startIndex <= endIndex) {
       let midIndex = Math.floor((startIndex + endIndex) / 2);

       if (array[midIndex] === target) {
           return midIndex;
       }

       if (midIndex < target) {
           startIndex = midIndex + 1;
       }

       if (midIndex > target) {
           endIndex = midIndex - 1;
       }
   }
   return null;
};

//test case
var findIndex = binarySearch([1, 2, 3, 4, 5], 8); //should return null

I'm working on a binary search algorithim for finding a target number in a sorted array. In my test case, I have a target that doesn't exist in the array argument and I expect it to return null. It works as expected but I'm not sure how the while condition exits out. This is my current logic about how it's working.

On the first loop, midIndex will be equal to 2; array[2] is less than 8 so startIndex is now 3, endIndex is still 4. On the second loop, midIndex will be equal to 3; array[3] is less than 8 so startIndex is now 4, endIndex is still 4. On the third loop, midIndex will be equal to 4; array[4] is not equal to 8. This is the part where I'm a bit confused. I thought my while condition would keep executing, even if there is nothing to run inside since the startIndex is the same as the endIndex causing an infinite loop but that doesn't seem to be the case. I don't have a conditional statement for if the startIndex === endIndex but I still get returned null when I run my code. Am I understanding this correctly that the while loop will stop even if it meets the while condition if there is nothing to execute within its scope?

1 Answers

Your loop terminates in the "not found" case because at some point, startIndex and endIndex are equal to each other but array[midIndex] is not equal to target, so you do either startIndex = midIndex + 1 or endIndex = midIndex - 1. At that point, startIndex is greater than endIndex (because they used to be equal), so your while condition startIndex <= endIndex becomes false.

Related