= Solution
Use <binary search> on an interval with unequal endpoint values. The <array> need not be sorted:
``
l := 0; r := n;
WHILE r-l > 1 DO
m := l + (r-l) DIV 2;
IF b[l] # b[m] THEN r := m ELSE l := m END
END;
k := l;
``
The <loop invariant> is
$$
0\leq l<r\leq n,\qquad b[l]\ne b[r].
$$
It holds initially by the given endpoint inequality, which also implies $n\geq1$. When $r-l>1$, $l<m<r$. If $b[l]\ne b[m]$, replacing $r$ maintains unequal endpoints. Otherwise $b[m]=b[l]\ne b[r]$, so replacing $l$ maintains them. This does not require monotonicity or even just two possible values.
The positive <integer> width $r-l$ is a <loop variant>, reduced to at most its old half rounded up. On exit $r=l+1$, giving
$$
\boxed{0\leq k<n,\qquad b[k]\ne b[k+1],\qquad T(n)=\Theta(1+\log n).}
$$
There are at most $\lceil\log_2 n\rceil$ iterations. The additive constant handles $n=1$.
Back to article page
