2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Thanks. Very clear and concise $\endgroup$
    – Gilboot
    Apr 25 at 18:02
  • $\begingroup$ "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]; "? $\endgroup$
    – John L.
    Apr 26 at 6:26
  • $\begingroup$ In that case, the entire function terminates, and control never reaches beyond the loop. $\endgroup$ Apr 26 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.