= Descending boundary search
{title2=$u[0..a)>z\geq u[b..n)$}
For a nonincreasing <array>, maintain indices $0\leq a\leq b\leq n$ such that entries before $a$ exceed the target and entries from $b$ onward are at most the target. Probe the middle of the half-open interval. A value above the target advances $a$ past that index; otherwise <set> $b$ to that index. The interval length decreases geometrically. At termination the common boundary is the first possible match, so one guarded equality test decides presence even with duplicates.
Back to article page
