Why do a "Lazy Binary Search"?

Question

Someone asked about Lazy Binary Searches today. Not knowing what that was, I looked for it, and found this post: What is Lazy Binary Search? Essentially, a Lazy Binary Search is a Binary Search where you compare for inequalities first, and only compare for equality once - at the end.

What's the point? Under what circumstances is checking if A<B easy to do, but checking if A=B is so hard you want to avoid it if possible?

Answer 1

It's one less comparison per iteration.

Of course, that's at the expense of a worse average runtime (you don't get the opportunity to return early).¹ But sometimes all you care about is worst-case runtime (consider hard-real-time applications, or a pipelined hardware implementation).

---

_{1. Although the asymptotic complexity doesn't change.}

Answer 2

One thing the lazy search does is find the first element in the sequence that's equal to the target (assuming the target is in the sequence).

If you have several elements that match the target, a non-lazy search would get you any one of those.

So, the C++ library's binary_search could be implemented as non-lazy (and I imagine it usually is), while lower_bound cannot.