Function RandomizedSelect

Data-Structures/Array/QuickSelect.js:22–32

(items, left, right, i)

}

function RandomizedSelect(items, left, right, i) {
  if (left === right) return items[left]

  const pivotIndex = RandomizedPartition(items, left, right)
  const k = pivotIndex - left + 1

  if (i === k) return items[pivotIndex]
  if (i < k) return RandomizedSelect(items, left, pivotIndex - 1, i)

  return RandomizedSelect(items, pivotIndex + 1, right, i - k)
}

function RandomizedPartition(items, left, right) {
  const rand = getRandomInt(left, right)