Search code examples
algorithmlanguage-agnosticbit-manipulationbinary-search

Fast average without division

I have a binary search loop which gets hit many times in the execution path.

A profiler shows that the division part of the search (finding the middle index given the high and low indices of the search range) is actually the most costly part of the search, by a factor of about 4.

(I think) it is not critical for efficient binary search to find the exact middle value, just a value near the middle which does not have bias in either direction.

Is there a bit-twiddling algorithm to replace mid = (low + high) / 2 with something much faster?

Edit: Language is C#, but the equivalent bit-operation is valid in any language (although it may be of no performance benefit), which is why I left the C# tag off.

Solution 
  • int mid = (low + high) >>> 1;

    Be advised that using "(low + high) / 2" for midpoint calculations won't work correctly when integer overflow becomes an issue.