Why is my javascript binary search erring?

Question

I wrote a binary search in javascript.

Array.prototype.binarySearch = function(find) {
  var low = 0, high = this.length - 1,
      i;
  while (low <= high) {
    i = Math.floor((low + high) / 2);
    if (this[i] > find) { low = i; continue; };
    if (this[i] < find) { high = i; continue; };
    return i;
  }
  return null;
}

It fails though to find 5 in my array of integers.

var intArray = [1, 2, 3, 5]

if (intArray.binarySearch(5))
  alert("found!");
else 
  alert("no found!");

Here is a Fiddle. http://jsfiddle.net/3uPUF/3/

Also, why do I have to define the method with Array.prototype.binarySearch? Why doesn't Array.binarySearch work? — dangerChihuahua007
– dangerChihuahua007, Commented Mar 15, 2012 at 3:09
may want to replace (low + high) / 2 with low + (high - low) / 2 to avoid overflow — turbanoff
– turbanoff, Commented Mar 15, 2012 at 3:09
read cockburn's "good parts" book. basically, that's where the language looks for these things. think of Array as just a function that makes new arrays; the new arrays delegate to Array.prototype and not to Array. that's just how it works. — andrew cooke
– andrew cooke, Commented Mar 15, 2012 at 3:12

Hunter McMillen · Accepted Answer · 2012-03-15 02:53:15Z

6

You have the logic backward for changing low and high, if this[i] > find then you want to look between 1 and i-1. If this[i] < find then you want to look between i+1 and the length of the array.

Try making these changes:

Array.prototype.binarySearch = function(find) {
  var low = 0, high = this.length - 1,
      i;
  while (low <= high) {
    i = Math.floor((low + high) / 2);
    if (this[i] == find) { return i; }; 
    if (this[i] > find)  { high = i - 1;};
    if (this[i] < find)  { low = i + 1;};
  }
  return null;
}

var intArray = [1, 2, 3, 5]
//index of the element in the array or null if not found    
alert(intArray.binarySearch(5));

answered Mar 15, 2012 at 2:53

Hunter McMillen

61.8k25 gold badges124 silver badges176 bronze badges

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

Comments

Jacob · Accepted Answer · 2012-03-15 02:52:51Z

3

Your comparisons are backwards. If the item that is found at i is greater than what you're looking for, then you want to adjust high, not low. See my updated jsFiddle.

answered Mar 15, 2012 at 2:52

Jacob

79k24 gold badges159 silver badges245 bronze badges

Collectives™ on Stack Overflow

Why is my javascript binary search erring?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related