How can we prove that in binary search, low – high ≤ 1
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 &gt; 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 &gt; h$, and so $l-h = 1$.