JavaScript binary search I wrote an implementation of binary search in JavaScript earlier for kicks, but I noticed my version was significantly different than those found on Google. Here is an example of binary search I found on Google (copied here to combat link rot): 

Array.prototype.binarySearch = function(find, comparator) {
    var low = 0, high = this.length - 1,
        i, comparison;

    while (low &lt;= high) {
        i = Math.floor((low + high) / 2);
        comparison = comparator(this[i], find);
        if (comparison &lt; 0) { low = i + 1; continue; };
        if (comparison &gt; 0) { high = i - 1; continue; };
        return i;
    }
    return null;
};


Most of the other implementations on Google are quite similar. But in mine, I don't subtract one from the low/high and continue from there. Instead, I divide the array in half and continue dividing the appropriate side in half until I reach the proper value. Code: 

function binary_search_iterative(arr, ele) {
    var beginning = 0, end = arr.length,
        target;
    while (true) {
        target = Math.floor((beginning + end) / 2);
        if ((target === end || target === beginning) &amp;&amp; arr[target] !== ele) {
            return -1;
        }
        if (arr[target] &gt; ele) {
            end = target;
        } else if (arr[target] &lt; ele) {
            beginning = target;
        } else {
            return target;
        }
    }
}


I wrote this recursive-style as well, but in testing I found this iterative version was faster.

In my tests, I've found that the examples I've found on Google (though they did not include the one above, they were nearly identical) are faster on smaller arrays, but as the input size increases, mine overtakes those. Since binary searches are usually limited (?) to larger input sizes, I see this as an improvement.

Is my thinking correct? Could this be done in an even better way? 

I also do not like this: 

if ((target === end || target === beginning) &amp;&amp; arr[target] !== ele) {
    return -1;
}


And I was curious if there is a good way to eliminate it or refactor the function where it's cleaner in general.
I would just like to hi-light a few points of difference in the two and how I think they are reflected in what you are seeing.


When making a comparison between arr[target] and ele, if they are not the same then you do not need to include target within the bounds of the next iteration (hence the +/- 1). This can reduce the number of comparisons though the effect is more significant on smaller datasets.
When following the above point, it becomes sufficient terminate as "not found" when beginning &gt; end rather then check that you are looking at the beginning or end value. Also your approach may provide a false negative when looking for "B" in the following situation.

    target
    |
    v
... A B
    ^ ^
    | |
    | end
    beginning


In this situation, because target === beginning and arr[target] !== B, it returns -1.
The googled code uses parseInt, I'm not sure how this affects correctness but I suspect this has an adverse effect on the performance.


I think what you are seeing in the scalability is because the googled code does fewer comparisons but the parseInt makes the comparisons more expensive. The reduced number of comparisons is more significant for small data sets, but for larger data sets cost of the comparison becomes more significant.

I would suggest some experimentation/investigation to see if this is accurate.