CODEWITHSUNDEEP
javascriptbinary-search
mega0319
mega0319

Reputation: 25

Infinite Loop with my binary search implementation in JavaScript

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
}

Upvotes: 0

Views: 389

Answers (2)

Alnitak
Alnitak

Reputation: 339786

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.

Upvotes: 4

Joey
Joey

Reputation: 670

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;
}

Upvotes: 1

Related Questions