Infinite Loop with my binary search implementation in JavaScript

Question

this is my first question on stack overflow so please bear with me. I wrote this binarySearch function and for some reason it hangs - I'm assuming because of an infinite loop. Can anyone find the faults with my code?

let binarySearch = (array, value) => {
 let target = value,
     start = 0,
     end = array.length - 1,
     middle = Math.floor( (end + start)/2 )

  while (start <= end){

    if ( array[middle] === target ){
      return true
    }else if (array[middle] < target){
      start = middle + 1
    }else if (array[middle] > target){
      end = middle - 1
    }    
  }
 return false
}

Notwithstanding whatever the bug is, a binary search algorithm should return the index of the found item (and undefined or similar if not found), not just a boolean to say whether the value was found or not. — Alnitak
– Alnitak, Commented Jul 3, 2017 at 16:21
Have you considered maybe logging the values of start, middle, and end to see what might be going on? — Pointy
– Pointy, Commented Jul 3, 2017 at 16:22
I recommend adding Alert at the beginning of the while loop to check the values each pass. You will probably find the issue easily. — Icculus018
– Icculus018, Commented Jul 3, 2017 at 16:26

Alnitak · Accepted Answer · 2017-07-03 16:36:02Z

4

The most obvious bug is that you need to calculate middle as the first operation inside the loop, not outside of it.

Without that change, you're always examining whichever element was "middle" when the function was first called, and never partitioning your search space.

With that fix in place, my tests indicate that the code works as required, although as suggested in the comments you should be returning the index of the found element, not simply a flag to say whether the element was found or not.

edited Jul 3, 2017 at 16:36

answered Jul 3, 2017 at 16:27

Alnitak

341k72 gold badges420 silver badges503 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

mega0319 Over a year ago

Ah I see. Thanks for the tip. Also, what if you wanted to use binary search in a way just to see if the element exists? Can you elaborate on why it should always be the index?

Alnitak Over a year ago

@mega0319 because with a binary search you get the index "for free", at which point an existence test is just a test for index < 0 or index !== undefined, depending on how you signal "not found". By all means wrap that separate test into a function of its own, but if the binary search tells you the index, why throw that information away?

Joey · Accepted Answer · 2017-07-03 16:32:28Z

1

An infinite loop occurs because the implementation shown is an iterative binary search, but the middle value is not recalculated upon each iteration, as others have mentioned. Thus, the middle variable will never change beyond the first iteration.

Below is an implementation which returns the index of value, or null, if value is not found.

function binarySearch(array, value) {
  let middle, start = 0,
    end = array.length - 1;

  while (start <= end) {
    middle = Math.floor((start + end) / 2);

    if (array[middle] > value) {
      end = middle - 1;
    } else if (array[middle] < value) {
      start = middle + 1;
    } else {
      return middle;
    }
  }
  return null;
}

answered Jul 3, 2017 at 16:32

Joey

6808 silver badges14 bronze badges

1 Comment

mega0319 Over a year ago

So obvious, yet I did not see it! Thanks!

Collectives™ on Stack Overflow

Infinite Loop with my binary search implementation in JavaScript

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related