> To begin with, when n is exactly 2^k-1, I would expect all the functions to show k comparisons, including Skarupke's. In the plot, all the curves overlap at 6

> To begin with, when n is exactly 2^k-1, I would expect all the functions to show k comparisons, including Skarupke's. In the plot, all the curves overlap at 64, 127 and 255 except Skarupke's which is off by 1. I'm afraid you misread the plot, although I admit it is hard to see. All the curves overlap at 31, 63, 127, etc, except Skarupke's. This is the raw data: https://gist.github.com/orlp/782369f5c047447bbaa924c13bdc6b35 https://gist.github.com/orlp/782369f5c047447bbaa924c13bdc6b3... The reason Skarupke's method is less efficient is because it does not take into account that the optimal size for binary search is 2^k - 1, so it is comparing at powers of two. This causes it to need an extra comparison, note the final line of the algorithm: return begin + comp(*begin, value); None of my methods have this extra comparison at the end. For simplicity, let's analyze n = 7 for Skarupke's method: size_t step = bit_floor(length); // step = 4 // First comparison. if (step != length && comp(begin[step], value)) { // For simplicity, let's assume the comparison fails. } // Second comparison. step /= 2; // step = 2 if (comp(begin[step], value)) begin += step; // Third comparison. step /= 2; // step = 1 if (comp(begin[step], value)) begin += step; step /= 2; // step = 0, break loop // Four comparison. return begin + comp(*begin, value); Oops, that's four comparisons instead of the optimal three.