Binary Search in Javascript

Question

I'm trying to implement a binary search algorithm in JavaScript. Things seem okay, but my return statements appear to be returning undefined? Can anybody tell what's wrong here?

Fiddle: http://jsfiddle.net/2mBdL/

Thanks.

var a = [     1,     2,     4,     6,     1,     100,     0,     10000,     3 ];  a.sort(function (a, b) {     return a - b; });  console.log('a,', a);  function binarySearch(arr, i) {     var mid = Math.floor(arr.length / 2);     console.log(arr[mid], i);      if (arr[mid] === i) {         console.log('match', arr[mid], i);         return arr[mid];     } else if (arr[mid] < i && arr.length > 1) {         console.log('mid lower', arr[mid], i);         binarySearch(arr.splice(mid, Number.MAX_VALUE), i);     } else if (arr[mid] > i && arr.length > 1) {         console.log('mid higher', arr[mid], i);         binarySearch(arr.splice(0, mid), i);     } else {         console.log('not here', i);         return -1;     }  } var result = binarySearch(a, 100); console.log(result); 

Answer 1

It's useful to write a search function in such a way that it returns a negative value indicating the insertion point for the new element if the element is not found. Also, using recursion in a binary search is excessive and unnecessary. And finally, it's a good practice to make the search algorithm generic by supplying a comparator function as a parameter. Below is the implementation.

function binarySearch(ar, el, compare_fn) {     var m = 0;     var n = ar.length - 1;     while (m <= n) {         var k = (n + m) >> 1;         var cmp = compare_fn(el, ar[k]);         if (cmp > 0) {             m = k + 1;         } else if(cmp < 0) {             n = k - 1;         } else {             return k;         }     }     return -m - 1; } 

This code with comments and a unit test here.

Answer 2

There are many workable solutions to this question, but all of them return early once they have found a match. While this might have a small positive effect on performance, this is negligible due to the logarithmic nature of binary search and can actually hurt performance if the comparison function is expensive to compute.

What is more, it prevents a very useful application of the binary search algorithm: finding a range of matching elements, also known as finding the lower or upper bound.

The following implementation returns an index 0 ≤ i ≤ array.length such that the given predicate is false for array[i - 1] and true for array[i]. If the predicate is false everywhere, array.length is returned.

/**   * Return 0 <= i <= array.length such that !pred(array[i - 1]) && pred(array[i]).   */  function binarySearch(array, pred) {      let lo = -1, hi = array.length;      while (1 + lo < hi) {          const mi = lo + ((hi - lo) >> 1);          if (pred(array[mi])) {              hi = mi;          } else {              lo = mi;          }      }      return hi;  }

Assume for the sake of argument that pred(array[-1]) === false and pred(array[array.length]) === true (although of course the predicate is never evaluated at those points). The loop maintains the invariant !pred(array[lo]) && pred(array[hi]). The algorithm terminates when 1 + lo === hi which implies !pred(array[hi - 1]) && pred(array[hi]), the desired postcondition.

If an array is sort()ed with respect to a comparison function compare, the function returns the smallest insert position of an item when invoked as

binarySearch(array, j => 0 <= compare(item, j)); 

An insert position is an index at which an item would be found if it existed in the array.

It is easy to implement lower and upper bound for an array in natural ordering as follows.

/**   * Return i such that array[i - 1] < item <= array[i].   */  function lowerBound(array, item) {      return binarySearch(array, j => item <= j);  }    /**   * Return i such that array[i - 1] <= item < array[i].   */  function upperBound(array, item) {      return binarySearch(array, j => item < j);  }

Of course, this is most useful when the array can contain several elements that compare identically, for example where elements contain additional data that is not part of the sort criteria.