Binary search that returns bitwise complement of missing index

Question

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 <= h) { m = (l + h) >> 1; comparison = typeof (comparator) == "undefined" ? (this[m] < target ? -1 : (this[m] > target ? 1 : 0)) : comparator(this[m], target); if (comparison < 0) { l = m + 1; continue; } else 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 (typeof (duplicate) == "undefined") duplicate = false; var i = this.binarySearch(target, comparator); if (i >= 0) { if (duplicate) { this.splice(i, 0, target); } } else { i = ~i; this.splice(i, 0, target); } return i; }; 

Answer 1

• 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 <= h) { m = (l + h) >> 1; comparison = comparator(this[m], target); if (comparison < 0) { l = m + 1; } else if (comparison > 0) { h = m - 1; } else { return m; } } return~l; }; function compareNumbers(a,b) { a-=b; return (a<0) ? -1 : ( a>0 ) ? 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.

Answer 2

I made several changes to the code based on GameAlchemist's advice and my own observations.

The improvements:

• Avoid calling Array.prototype directly, which pollutes the enumerable keys in the array such that (for i in arr) loops mistakenly treat the new array methods as array items. Use Object.defineProperty instead
• Avoid typeof(comparator)==="undefined", which could be expensive, and pull the comparator check out of the inner while loop so it's only called once per binarySearch
• Remove unnecessary continue's from binarySearch method
• Use (l+h)>>>1 (unsigned bitwise rightshift) instead of (l+h)>>1 (plain ol' bitwise rightshift) to avoid problem with large numbers (between 2147483647 and 4294967290) being interpreted as negatives.
• Setting a variable to false if it is undefined is redundant. Remove unnecessary typeof(boolean)==="undefined" check from binaryInsert method

Updated Code:

Object.defineProperty(Array.prototype, "binarySearch", { value: function (target, comparator) { var l = 0, h = this.length - 1, m, comparison; comparator = comparator || function (a, b) { return (a < b ? -1 : (a > b ? 1 : 0)); }; while (l <= h) { m = (l + h) >>> 1; comparison = comparator(this[m], target); if (comparison < 0) { l = m + 1; } else if (comparison > 0) { h = m - 1; } else { return m; } } return~l; } }); Object.defineProperty(Array.prototype, "binaryInsert", { value: function (target, duplicate, comparator) { var i = this.binarySearch(target, comparator); if (i >= 0) { if (!duplicate) { return i; } } else { i = ~i; } this.splice(i, 0, target); return i; } }); 

Note for Old Browsers: Above code only works in IE9 and up. I've noticed that Object.defineProperty works only on DOM elements in Internet Explorer 8, so to work around that I can wrap the above in a try/catch and if it throws an exception just use my old key-polluting method of calling Array.prototype directly.

Also note that this code will start to behave incorrectly when the array length exceeds 4294967290. Alas! Such is the price I pay for using the more efficient (l+h)>>>1 instead of the more reliable Math.floor((l+h)/2)