I took a stab at the same problem a while ago. Since the upper bound of iterations is based on the input length, if you write your search in a way that extra iterations don't change the result, you can use a switch fallthrough to "unroll" the loop and not have to branch.

https://github.com/ehrmann/branchless-binary-search/blob/mas...

That particular branch is well-predicted for long arrays. You probably only gonna have a single misprediction for the complete binary search function, the performance consequence of that branch is negligible.

People (and compilers, too) don’t write branchless code just for the sake of it, they do because it helps with performance.

This is literally addressed in the article:

    More branchless, more better?
    Short answer: no. This section can be skipped but here’s the long answer: For n elements where 2k <= n < 2k+1 sb_lower_bound will always do k+1 comparisons. On a 64-bit machine that means at most 64 iterations of the while (length > 0) loop. So it’s possible to write a “fully branchless” version that doesn’t have the length check by using a switch with intentional fall-through.
    
    size_t length = last - first;
    size_t rem;
    switch(std::bit_width(length)) {
       case 64:
          rem = length % 2;
          length /= 2;
          first += comp(first[length], value) \* (length + rem);
       case 63:
          rem = length % 2;
          length /= 2;
          first += comp(first[length], value) \* (length + rem);
       // ...
       case 1:
          rem = length % 2;
          length /= 2;
          first += comp(first[length], value) \* (length + rem);
    }
    return first;
    
    If you’re not familiar with switch, think of it as a jump into code. In our case to the exact place from which there are exactly the right number of comparisons left to do.
    
    “Is it any faster?” No. Modern x86 processors handle loop conditions well as they’re predictable; we’re very likely to remain in the loop. And that’s good especially because it saves us from writing templates or macros or copy-paste-edit the 64 cases.

(Maybe people will RTFA if I paste it into the comments.)

Because that's a branch that's "always" taken, except for once - which, speed-wise, is very close to always taken, i.e. not a branch. The author counts the branching inside the loop, which is often taken and often not taken.

the article covers that right at the top: “branchless” because the if compiles down to a conditional move instruction rather than a branch/conditional jump.