Function kthNumber

math/kthnumber.go:25–43

kthNumber use the selection algorithm (based on the partition method - the same one as used in quicksort).

(nums []int, k int)

// kthNumber use the selection algorithm (based on the partition method - the same one as used in quicksort).
func kthNumber(nums []int, k int) (int, error) {
	if k < 0 || k >= len(nums) {
		return -1, search.ErrNotFound
	}
	start := 0
	end := len(nums) - 1
	for start <= end {
		pivot := sort.Partition(nums, start, end)
		if k == pivot {
			return nums[pivot], nil
		}
		if k > pivot {
			start = pivot + 1
			continue
		}
		end = pivot - 1
	}
	return -1, search.ErrNotFound
}