while(l < r) vs. while(l <= r) advantages/disadvantages in binary search

Question

There many many ways to code binary search, but one of the main distinctions I've seen in people's code is one group of people use while(l < r) and another uses while(l <= r). I personally use the latter.

Is there any advantages/disadvantages to using either? I've never used while(l < r), so when I see it, it's not always clear to me how it guarantees correctness.

Answer 1

Binary search may be a name for some specific algorithm, but more often it is seen as a generic approach. Namely, you repeatedly subdivide the search space into two halves and then disregard the one which is known not to contain the solution. What exactly you put into the code depends on the context and on the details of your proof of correctness, as you seem to have noticed.

For example, in the following contexts neither while (L < R) nor while (L <= R) makes much sense:

1. Finding a zero of a continuous monotone function uses either while(abs(R - L) > eps) or simply fixed number of iterations.
2. Finding an integer bit-by-bit from the most significant to the least significant doesn’t have “left” or “right” indices.
3. https://en.wikipedia.org/wiki/Level_ancestor_problem#Jump_pointer_algorithm also doesn’t require having two pointers.

The textbook binary search is derived from maintaining (a variation of) these conditions throughout the runtime of the search:

1. $L < R$
2. Probe is taken strictly between $L$ and $R$
3. $P(L)$ is always false
4. $P(R)$ is always true

On integer domains this yields the following algorithm for boundaries $L$, $R$ and a function (or “predicate”) $P$:

ensure P(L) is false
ensure P(R) is true

while R - L > 1 do
  M = (L + R) / 2

  if P(M) is false,
    L := M
  otherwise,
    R := M

This algorithm is guaranteed to end with $L$ and $R$ “sticking together”, where $L$ points to “false” and $R$ points to “true”, thus finding the boundary where the function $P$ changes its value. The only tricky part is to prove that $M$ indeed never equals $L$ or $R$ (otherwise the algorithm may get stuck). This property of $M$ also allows to avoid invariant checks before the while loop: we can simply move boundaries one step outside, for we know they’ll never be probed.

L := L - 1
R := R + 1

while R - L > 1 do
  M = (L + R) / 2

  if P(M) is false,
    L := M
  otherwise,
    R := M

I don’t know any direct derivation of the other variants, but you can easily get them using simple substitutions. If you want while (L < R) in your code, just rearrange $R - L > 1$ into $L < R - 1$ and then call $R - 1$ the new $R’$:

while L < R’ do
  M = (L + R’ + 1) / 2

  if P(M) is false,
    L := M
  otherwise,
    R’ := M - 1

If you want while (L <= R), then you first change $R - L > 1$ into $R - L \geq 2$, which can be rearranged as $L + 1 \leq R - 1$, and then $L’$ is $L + 1$, and $R’$ is $R - 1$.

while L’ <= R’ do
  M = (L’ + R’) / 2

  if P(M) is false,
    L’ := M + 1
  otherwise,
    R’ := M - 1

All three versions are behaviourally the same, so the question is whether you see the correctness of your particular version easily and how well it fits in the context.