Compare values directly, avoiding subtraction that could overflow:Each branch returns an index whose value lies between the other two sampled values. Non-strict comparisons make ties harmless. 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.
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
}
} Articles by others on the same topic
There are currently no matching articles.