Efficient Binary Search

Question

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.

Answer 1

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 algorithms, 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 :-)

Answer 2

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. *

Answer 3

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.

Answer 4

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 )
   add largest-mid-point to mid-point
if key less than value at ( mid-point + 2nd-largest-mid-point )
   add 2nd-largest-mid-point to mid-point
if key less than value at ( mid-point + 3rd-largest-mid-point )
   add 3rd-largest-mid-point to 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. \$\frac{a - b}{c - b} = \frac{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.

Answer 5

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.

Answer 6

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).

Answer 7

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.