# Efficient Binary Search

My implementation:

Array.prototype.binarySearchFast = function(search) {

var size = this.length,
high = size -1,
low = 0;

while (high > low) {

if (this[low] === search) return low;
else if (this[high] === search) return high;

target = (((search - this[low]) / (this[high] - this[low])) * (high - low)) >>> 0;

if (this[target] === search) return target;
else if (search > this[target]) low = target + 1, high--;
else high = target - 1, low++;
}

return -1;
};


Normal Implementation:

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


The difference being my implementation makes a guess at the index of the value based on the values at the start and end positions instead of just going straight to the middle value each time.

I wondered if anyone could think of any case scenarios where this would be slower than the original implementation.

UPDATE: Sorry for the bad examples. I have now made them a little easier to understand and have setup some tests on jsPerf. See here:

http://jsperf.com/binary-search-2

I'm seeing about 75% improvement by using my method.

-
I'm sorry, but information theory dooms your attempt. The only way to speed up the binary search is by making assumptions about the kind of data you are storing. – Winston Ewert Oct 14 '11 at 21:49
You'll get a performance boost by changing: Math.floor((low + high) / 2) to: (low + high) >> 1 – Sandro Pasquali Feb 5 '12 at 17:25
Maybe so, but the (very) minor performance gain you may get from this almost certainly isn't worth the reduced readability. – sepp2k Feb 5 '12 at 18:08
That's always the question, isn't it... Nevertheless, perhaps the goal for a binary search is always maximum speed? – Sandro Pasquali Feb 8 '12 at 12:11
I believe what you're doing is called an interpolation search. en.wikipedia.org/wiki/Interpolation_search – user18524 Oct 19 '12 at 23:25

My advice is to not mess about with something that's been well and truly tested :-)

No, not really: if you find an algorithm that's better then, by all means, use it. However, in this case, for general data, this isn't going to be an improvement.

The power of binary search, and other O(log N) type algorihtms, lies in the fact that you dispose of half the remaining search space with each iteration. In other words, if the initial search space (array size) was 1000, the first iteration removes 500 of them.

Any change to the "midpoint" (the divider between what you're keeping in the search space and what you're disposing of) that you select during an iteration has the potential to improve or degrade the performance. For example, putting the midpoint at 25% has the potential to reduce the search space even faster (if you're right) or slower (if you're wrong).

Now, if you know of some property of the data, you can use that to your advantage to improve an algorithm. In fact, it's the "extra" knowledge about your list (the fact that it's sorted) that allows you to optimise what would normally be a sequential search into a binary one.

So it all comes down to how good your extra information is. In this case, the values of the two end nodes alone are not really indicative of where the midpoint should be. You only have to look at the list [1,2,3,4,5,6,7,8,9,10,11,12,13,14,500,1000] to see this in action.

If you were looking for 500 in that list, you might decide that, based on the first and last elements being 1 and 1000, it would be in the middle somewhere, which is clearly not the case.

Similarly, if you were looking for 14, you might first check elements around the 1.4% mark (14/1000) which would probably be the first element, despite the fact it's right up at the other end.

Of course, that's not to say that other extra information would not help. If you knew that the data was fairly evenly distributed over the range, then your improvement may be worth it.

You also need to be aware that it's usually only going to be important with large data inputs, so it may not necessarily be worth it even if it turns out to be much better. Even bubble sort is blindingly fast for 100 elements :-)

-

I thought that I should test them, but then I notices that neither implementation takes a parameter so they don't know what to look for...

Anyway, the "fast" implementation would be slower whenever you don't have an even distribution in the array. For example looking for 5 in [1,2,3,4,5,6,7,10000] would make something like four iterations instead of one.

-
I've now fixed the algorithm to try and avoid that being an issue. – Oliver Morgan Oct 14 '11 at 19:47
@OliverMorgan: Just adding another value to the test array makes the "fast" search as slow as indexOf: jsperf.com/binary-search-2/2 – Guffa Oct 14 '11 at 20:57

Check this out http://en.wikipedia.org/wiki/Interpolation_search

Particularly the paragraph that states:

Each iteration of the above code requires between five and six comparisons (the extra is due to the repetitions needed to distinguish the three states of < > and = via binary comparisons in the absence of a three-way comparison) plus some messy arithmetic, while the binary search algorithm can be written with one comparison per iteration and uses only trivial integer arithmetic. It would thereby search an array of a million elements with no more than twenty comparisons (involving accesses to slow memory where the array elements are stored); * to beat that the interpolation search as written above would be allowed no more than three iterations. *

-

If you want to speed up a binary search, "unroll" the loop. For 1,000 items you are looping 10 times. 10 discreet pieces of code remove the "looping overhead". If you have a specific search rather than a general, you can replace all range calculations with literal values (otherwise replacing them with a variable).

Set the mid-point "low"

if key less than value at ( mid-point + largest-mid-point )
if key less than value at ( mid-point + 2nd-largest-mid-point )
if key less than value at ( mid-point + 3rd-largest-mid-point )
etc


Developed 31 years ago with Cobol, discovered later in Jon Bentley's Programming Pearls book (and is probably the answer to Exercise 24 in Knuth's Sorting and Searching on binary searches).

Still works, in Cobol, today :-)

Due to the "powers of two" it works with even very large tables without vast amounts of extra code.

EDIT: I always used a "binary" number of entries in my tables for searching. Bentley shows 1000 entries, "tying" the mid-point amendments to the right boundary so as not to go "outside" the table. This gives an "overlap" using binary mid-points, but implications of that vs actual midpoints I haven't had a chance to look at.

I can get substantial improvements over the "standard" with this, as Bentley suggests we should expect. I also used a couple of other "tweaks" but these are perhaps related too closely to Cobol.

EDIT: Since "unwinding" is no use to a modern language, and bearing in mind I don't know how "expensive" these may be for you, or whether they apply to JavaScript and tiny instruction caches, but:

if (this[target] === search) return target;
else if (search > this[target]) low = target + 1, high--;
else high = target - 1, low++;


1) You test for equality first. Equality is the least likely outcome, so this should be re-ordered (you changed the order from your "normal" implementation). 2) "low = target" I assume would be faster "than low = target + 1", similar for the minus. "high--" is slower than leaving "high" alone altogether, similar for the "high++". You rely on the "crossover" these cause to terminate the search with failure. If you work out another, simpler, way to terminate the search, you might save a few instructions from the precious cache.

(((search - this[low]) / (this[high] - this[low])) * (high - low))

3) ( a - b ) / ( c - b ) = ( a / c ) - b 4) Doing two tests for equality on the extremes of the range gives you what? You get more inequality than equality in a binary search, so rather than speeding up, this slows down (subject to cache considerations, maybe). 5) If you let the loop terminate "naturally" (meaning you find out how, as mentioned above) you can remove the remaining test for equality from within the loop.

Obviously with such a language and cache limitations none of the above may work.

OK, there's a good deal of irony here. These are some things you may investigate to see where they may lead you. They may all be useless to you, but you never know until you try. Or do you? There's that irony again.

-
I would be careful with loop unrolling optimizations like this one, because they can actually have worse performance, especially in a higher-level language like JavaScript. Especially when you consider that more code means that cache misses happen more often (“ancient” Cobol programmers didn't have to worry about caches, I belive). – svick Jan 28 '13 at 17:27
Wow! Used to be you had to be careful with code size... seems not much progress... I suppose your code is longer than my 698 bytes, for a table with 262144 entries :-) Are you telling me you code to keep as much as possible in "cache" and then your programs run like dogs if you're not successful? Very strange. Interesting to know. Usually there will be much more code in our programs than the binary search. Perhaps it still fits in "our" caches anyway? – Bill Woodger Jan 28 '13 at 19:15
That's not what I'm saying at all. Yes, usually there will be much more code in your program, so the performance of binary search won't matter much (because it's already very fast). I'm just saying you shouldn't be that eager with Cobol-era optimizations (especially if they make your code less maintainable), because it's quite possible they will actually make your code slower. – svick Jan 28 '13 at 19:23
Well, I was just tossing it in the mix. If it's no good for JavaScript, that's OK with me. On "maintainable" you have to remember 1) it will not need maintenance (famous last words) and 2) with good naming, comments and documentation, it can be made very clear what is going on. Which bits do you leave out (perhaps you use very short names to ensure the "language processor" can make use of the cache?) to make you think it can't be maintained? As I said, it works today, so not sure what the "Cobol-era" might mean. – Bill Woodger Jan 28 '13 at 19:45

The Normal implementation is shorter and easier to follow.

To convert the Normal to your "guess" version, it is only necessary to change one line - the line where i is assigned to the midpoint. The rest of your changes try to short-circuit the search when one of your variables lands directly on the index of the item you're searching for, and in my opinion these extra checks will slow it down more often than they'd speed it up.

By trying to guess at the optimal partition, you're doing a trade-off which will give better best-case performance but worse worst-case performance. You'd need to test this with a wide range of input to see if it really helps.

-

Updated: based on your description, it's easy to derive a scenario where your algorithm turns into a linear search rather than a binary one. Just set up one equation per step that it would take and solve them simultaneously.

Your code is still buggy, by the way. If you search for a value smaller than all existing values then you'll get target set to a negative index. In general, there's no guarantee that target will be between low and high, and if it isn't bad things happen (like the space you're searching getting larger. With a bit of effort it might be possible to design a case where your current version loops forever).

-
Sorry for the mistakes in the code - I was in a rush and didn't expect such a quick reply. I have now fixed the examples and uploaded a benchmark - let me know what you think of the results. – Oliver Morgan Oct 14 '11 at 19:48

Did you try to execute the algorithm with an array that has only 1 element (e.g. A=[1])? If you search for the value 1, it'll give false, or in this case -1, because low == high and the loop body is never entered despite the value 1 being part of the array. It might be faster, but will fail to deliver the right answer for at least one case.

-