My version: template <class T> INLINE size_t fast_upper_bound5(const vector<T>& vec, T value) { size_t index = 0; size_t size = vec.size();

My version: template <class T> INLINE size_t fast_upper_bound5(const vector<T>& vec, T value) { size_t index = 0; size_t size = vec.size(); while (size > 0) { size /= 2; size_t probe = index + size; if (vec[probe] <= value) index = probe + 1; } return index; } Slightly faster with gcc: $ g++-mp-4.9 -std=c++11 -O3 -DNDEBUG -o blog blog.cpp $ ./blog size = 8192: stl : 144.883 miliseconds version 1: 145.406 miliseconds version 2: 129.713 miliseconds version 3: 109.231 miliseconds version 4: 103.578 miliseconds version 5: 102.282 miliseconds But sucks with clang, apparently because of the described problem with non-using cmov instruction. $ clang++-mp-3.6 -std=c++11 -O3 -DNDEBUG -o blog blog.cpp $ ./blog size = 8192: stl : 147.466 miliseconds version 1: 145.978 miliseconds version 2: 145.547 miliseconds version 3: 113.546 miliseconds version 4: 106.968 miliseconds version 5: 144.231 miliseconds