How can we prove that in binary search, low – high ≤ 1

How can we prove that in binary search

$$\mathit{low} - \mathit{high} ≤ 1$$

Below is a sample algorithm for Binary Search.

while (low<=high) {
int mid = low + (high-low)/2;
if (data[mid]<value) low = mid+1;
else if (data[mid]>value) high = mid-1;
else return &data[mid];
}
return nullptr;


A good stranger told me that

typically you would want to avoid unprotected mid-1 and mid+1 for fear of over- and underflow and have a special case for when the difference between high and low is less than 2.

What I still want to know is a formal proof that $$\mathit{low} - \mathit{high} ≤ 1$$ provided that you started off with $$\mathit{low} ≤ \mathit{high}$$.

My idea so far has been to adapt the explanation on loop invariant here but I can assure you I haven't made any progress, yet.

Let's denote the indices by $$l,h,m$$. If $$l \leq h$$ and $$h-l$$ is even then $$m = \frac{l+h}{2}$$ and so in the following iteration, the new values $$l',h'$$ will either be $$\frac{l+h}{2}+1,h$$ or $$l,\frac{l+h}{2}-1$$. In the first case $$l'-h' = \frac{l-h}{2}+1 \leq 1,$$ and in the second case $$l'-h' = \frac{l-h}{2}+1 \leq 1.$$

If $$l \leq h$$ and $$h-l$$ is odd then $$m=\frac{l+h-1}{2}$$ and so either $$l',h' = \frac{l+h+1}{2},h$$ or $$l',h' = l,\frac{l+h-3}{2}$$. In the first case $$l' - h' = \frac{l-h+1}{2} \leq \frac{1}{2}$$ and so $$l'-h' \leq 0$$, since $$l'-h'$$ is an integer. In the second case $$l' - h' = \frac{l-h+3}{2} \leq \frac{3}{2},$$ and so $$l'-h' \leq 1$$, since $$l'-h'$$ is an integer.

Put together, we have shown:

If $$l \leq h$$ then $$l'-h' \leq 1$$.

Now let's use it to show that $$l-h \leq 1$$ always holds.

We first prove by induction on $$t$$ that if the loop executes at least $$t$$ times, then after $$t$$ iterations of the loop, $$l-h \leq 1$$. The base case $$t = 0$$ is by assumption. Now suppose that after $$t$$ iterations, we have $$l-h \leq 1$$. If $$l > h$$ then the loop terminates, and so there is nothing to prove. Otherwise, $$l \leq h$$, and so $$l-h \leq 1$$ at the end of the iteration, as shown above.

This shows that when the loop terminates (if it terminates — which has to be shown separately), $$l-h \leq 1$$ necessarily holds. In fact, we can say more: since the loop terminated, we must have $$l > h$$, and so $$l-h = 1$$.

• Thanks. Very clear and concise Apr 25 at 18:02
• "In fact, we can say more: since the loop terminated, we must have $l\gt h$, and so $l-h=1$". Did you ignore the clause "else return &data[mid]; "? Apr 26 at 6:26
• In that case, the entire function terminates, and control never reaches beyond the loop. Apr 26 at 6:28