= Solution
Compare values directly, avoiding subtraction that could overflow:
``
def bestIndex(l: Int, r: Int): Int = {
require(0 <= l && l < r && r <= a.length)
val first = l
val middle = l + (r - l) / 2
val last = r - 1
if (a(first) <= a(middle)) {
if (a(middle) <= a(last)) middle
else if (a(first) <= a(last)) last
else first
} else {
if (a(first) <= a(last)) first
else if (a(middle) <= a(last)) last
else middle
}
}
``
Each branch returns an index whose value lies between the other two sampled values. Non-strict comparisons make ties harmless. \b[The <precondition> is a nonempty valid segment], not a segment of at least three elements: for lengths one or two some sample indices coincide, but the code still returns a valid median of the sampled triple. This matters because selection can reach a two-element segment. With three distinct sample values, the pivot is not the minimum or maximum of the whole segment, but it need not be near the segment's true median. <Median-of-three pivot selection> is a heuristic, not a balance guarantee.
Back to article page
