Binary search that returns bitwise complement of missing index

While re-writing some old JavaScript code to better handle large arrays, I ended up writing my own binary search method.

I found many examples of binary search methods written in JavaScript, but all the examples I found returned -1 whenever the target was not found in the array. What I really wanted was the bitwise complement of the index where the target belonged if it did not exist in the array, like the BinarySearch method on generic lists in .NET.

This is the code I ended up writing, but I'm curious if I've overlooked any potential performance problems or logic errors. To the best of my knowledge, the code works sufficiently as designed (see my fiddle). Please help me review this code and verify that it follows common best practices.

binarySearch Method

Inputs: target: the object being sought in the array;
comparator: (optional) comparison method

Returns: If positive or zero, the index of the item in the array. If negative, the bitwise complement of the item's proper location in the array.

Array.prototype.binarySearch = function (target, comparator) {
    var l = 0,
        h = this.length - 1,
        m, comparison;
    while (l > 1;
        comparison = typeof (comparator) == "undefined" ? (this[m]  target ? 1 : 0)) : comparator(this[m], target);
        if (comparison  0) {
            h = m - 1;
            continue;
        } else {
            return m;
        }
    }
    return~l;
};

Using the above, I also wrote a binary insert method, which adds an item to the correct location in an array. I'm curious about this also, and whether there's anything I can do to improve its performance or handle any edge case bugs.

binaryInsert Method

Inputs: target: object being inserted; duplicate: (optional) whether to add if it already exists in the array (false by default); comparator: (optional) comparison method

Returns: Index of new item added to array

```
Array.prototype.binaryInsert = function (target, duplicate, comparator) {
if

• First comment is about the way you are adding the functions to the Array prototype : by just adding them this way, you 'pollute' the keys of the array, so anyone doing a for ... in for instance will enumerate also on the added functions.

-->> Use Object.defineProperty to have those function non enumerables.

The pattern could look like :

(function () {

    var newArrayMethods = {
        //  Returns a shallow copy of this array
        copy: function () {
            return this.slice(0);
        },

        // Returns true if this array contains 'element', returns false otherwise
        contains: function (element) {
            return this.indexOf(element) >= 0 ;
        }            
    }

    // let's install those methods on the prototype
    for (var newMethodName in newArrayMethods) {
        installFunction(newMethodName, newArrayMethods[newMethodName]);
    }

    function installFunction(name, fn) {
        if (Array.prototype[name]) throw ('Array method ' + name + '() already defined.');
        Object.defineProperty(Array.prototype, name, {
            value: fn
        });
    }

})();

• Second thing is that typeof is slow : you don't want to use it within a loop.

The code below also avoids one branch per loop.

function binarySearch (target, comparator) {
    var l = 0,
        h = this.length - 1,
        m = 0, 
        comparison = 0;
   comparator = comparator || compareNumbers ;

    while (l > 1;
        comparison = comparator(this[m], target);
        if (comparison  0) {
            h = m - 1;
        } else {
            return m;
        }
    }
    return~l;
};

function compareNumbers(a,b) { a-=b;  return (a0 ) ? 1 : 0 ;  } ;

• Array.splice is to be avoided if you seek performances : it is slow and creates garbage.

Do the insertion yourself.

I wrote below insertion function moving forward, to avoid cache miss.

You'll notice i changed the insert function signature so it is more alike to the search (target + comparator arguments first).

Also no need to process an argument that defaults to false.

function binaryInsert(target, comparator, duplicate) {
    var i = this.binarySearch(target, comparator);
    if (i >= 0 ) {
        if (!duplicate) return i;
    } else {
        i = ~i;
    }
    insertOneAt(this, target, i);
    return i;
};

function insertOneAt(arr, item, index) {
    var tmp1=item, tmp2=item;
    var len = arr.length;
    for (; index<=len; index++) {
       tmp2 = arr[index]
       arr[index]=tmp1;
       tmp1=tmp2;
    } 
}

• Detail : change your binaryInsert comment about the return value to something like :

Returns: Index of new item added to array, or of the existing item if duplicate==false and the item was found.

• You have also some decision/changes to make about the way you handle duplicates in your search.

As of now search returns any matching item's index (compare==0), it does not ensure, for instance, that it is the smallest index.

If it's ok just mention it, otherwise you have to change a bit your search.

Since the insert relies on search, your decision on the search will affect insert's semantic as well.

StackExchange Code Review Q#82011, answer score: 2