The setup code to reduce the length to a 2-power can be avoided. I'm curious how well the following code performs in comparison: for (size_t length = end -

The setup code to reduce the length to a 2-power can be avoided. I'm curious how well the following code performs in comparison: for (size_t length = end - begin; length != 0; length = (length + 1) / 2) { size_t step = length / 2; if (compare(begin[step], value)) begin += step; } return begin; For odd lengths like 5, this splits the array in an even part of length 2, and an odd part of length 3, and then searches either part with length 3. So again there is some redundancy for non-2-powers. While this code is simpler, it does require an extra division and increment in each loop iteration, so presumably it performs a little worse.