= Solution
A second <binary search> locates the first entry strictly greater than `x`:
``
def upperBound(a: Array[Int], x: Int): Int = {
require(a != null) // a is nondecreasing
var lo = 0
var hi = a.length
while (lo < hi) {
val mid = lo + (hi - lo) / 2
if (a(mid) <= x) lo = mid + 1
else hi = mid
}
lo
}
def equalRange(a: Array[Int], x: Int): (Int, Int) =
(lowerBound(a, x), upperBound(a, x))
``
For <upper-bound search>, the <loop invariant> is $0\leq lo\leq hi\leq n$, $a[0..lo)\leq x$, and $x<a[hi..n)$; its <loop variant> is again $hi-lo$. The same midpoint and sortedness arguments prove preservation, termination and $O(\log(n+1))$ <time complexity>. The first <binary search> in part (b) already has its own <loop invariant> and <loop variant>.
Let the two boundaries be $i,j$. There cannot be a value greater than $x$ before the first value at least $x$, so $i\leq j$. Every entry between them is simultaneously at least and at most $x$, hence equals $x$. Entries before $i$ are smaller and entries at or after $j$ are larger, so the interval cannot be extended at either end. This proves the <equal-range search> result is maximal. \b[If `x` is absent, `i == j`, both equal to its insertion position]; this can be zero, $n$, or an interior gap. Two logarithmic searches still have logarithmic total <time complexity>. Computing an upper boundary as `lowerBound(a, x+1)` would introduce an unnecessary <integer overflow> bug at the largest <integer>.
Back to article page
