How can I optimize binary search?

Question

I have been thinking on how my binary search can be optimized. The code follows. What I have done so far:

All I could think of was in terms of handling different inputs.

Optimized worst case(one of the worst cases) when element being searched is out of bounds, i.e. searching a number lower than the lowest or higher than the highest. This saves O(logn) comparisions when it is a guarantee it won't be found in the input.

int input[15] = {1,2,2,3,4,5,5,5,5,6,7,8,8,9,10};
/*
 * Returns index p if a[p] = value else -ve int.
 * value is value being searched in input.
 */
int
binary_search (int * input, int low, int high, int value)
{
    int mid = 0;
    if (!input) return -1;
    if (low > high) return -1;

    /* optimize worst case: value not in input */
    if ((value < input[low]) || (value > input[high]))
    { return -2; }

    mid = (low + high)/2;

    if (input[mid] == value) {
        return mid;
    }
    if (input[mid] > value) {
        return binary_search(input, low, mid -1, value);
    } else {
        return binary_search(input, mid+1, high, value);
    }
}

Another worst case I can think of is when value being searched is next to the mid of the input or the first element. I think more generalized is the lower / higher bounds of input to each call of binary_search. This also requires the algorithm to take exact logn comparisons.

Any other suggestions on what other areas I can focus on improving. I don't need the code but a direction would be helpful. Thanks.

The best optimizations for binary search in my opinion are not to use it at all for n < 1,000 (as O(log(n)) and O(n) are more or less the same anyway thanks to cache misses), and on large datasets prefetch 3 or 4 subdivisions speculatively per iteration (easy since these are known ahead of time). — Damon
– Damon, Commented Nov 16, 2013 at 23:33
Obvious one: rewrite the recursion to iteration. Your compiler might do it, but there's no guarantee. — user555045
– user555045, Commented Nov 17, 2013 at 8:11

Raymond Hettinger · Accepted Answer · 2013-11-16 23:17:46Z

3

Jon Bentley's Programming Pearls has a nice chapter on optimizing binary search. See Chapter 4 in http://www.it.iitb.ac.in/~deepak/deepak/placement/Programming_pearls.pdf

One of the variants is amazingly efficient (see page 87 in the chapter on "Code Tuning"):

# Search a 1000-element array
l = 0
if x[512] < t: l = 1000 + 1 - 512
if x[l+256] < t: l += 256
if x[l+128] < t: l += 128
if x[l+64] < t: l += 64
if x[l+32] < t: l += 32
if x[l+16] < t: l += 16
if x[l+8] < t: l += 8
if x[l+4] < t: l += 4
if x[l+2] < t: l += 2
if x[l+1] < t: l += 1
p = l + 1
if p > 1000 or x[p] != t:
    p = 0                   # Not Found

edited Nov 16, 2013 at 23:17

answered Nov 16, 2013 at 23:06

Raymond Hettinger

229k67 gold badges405 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

SeattleOrBayArea Over a year ago

I have a copy of Programming Pearls. Is the link legal? Also, which variant are you referring to, I am solving problems given in column 4.

Raymond Hettinger Over a year ago

Really? You just downvoted one of the best works in computer science, one that specifically addresses the question of how to optimize binary searches. BTW, I don't know about the link -- it was the first hit on Google. If you own the book, you should reference it directly.

SeattleOrBayArea Over a year ago

Nope that was for the link but I upvoted after I saw your edit. Sorry about that.

Sneftel · Accepted Answer · 2013-11-16 22:23:26Z

3

An optimization of the sort you're considering -- handling a special case -- will inevitably make you spend more time in the OTHER cases. Your "worst case" optimizations have made them into the best cases, but at the cost of creating other worst cases. And in this instance you've made two cases into "best cases", and n/2 cases into "worst cases" which previously were not. You've slowed everything else down.

(Especially in this instance, because you're checking for too low / too high on every single recursion.)

If you actually expect -- in your particular use case -- that the search will mostly be searching for values that are too low or too high, this might be a good idea. As a general rule of thumb, though, the fastest implementation is the simplest one.

answered Nov 16, 2013 at 22:23

Sneftel

41.9k13 gold badges78 silver badges112 bronze badges

1 Comment

SeattleOrBayArea Over a year ago

Yes, agree with you. In general such searches for too low / high will be rarer.

Collectives™ on Stack Overflow

How can I optimize binary search?

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related