Skip to main content

1 August 2020, 3:34 pm

Is It Possible to Implement Faster Binary Searches?

Is It Possible to Implement Faster Binary Searches?

Last week Slashdot reader scandum described the search for the most efficient sorting algorithm. Now he's back, touting a new implementation for binary searches (using the same GitHub repo, and written in 15 to 30 lines of C code) that he says may be "up to 40%" faster for 32-bit integers. ("Keep in mind performance will vary depending on hardware and compiler optimizations.") The most commonly used binary search variant was first published by Hermann Bottenbruch in 1962 and hasn't notably changed since. Binary searches are one of the corner stones of computer science... The reason the algorithms are faster appears to be a combination of simpler calculations, branch prediction, and a reduction in cache misses.

Read more of this story at Slashdot.