Class BFPRT

src/main/java/com/thealgorithms/others/BFPRT.java:9–178

The BFPRT (Median of Medians) algorithm implementation. It provides a way to find the k-th smallest element in an unsorted array with an optimal worst-case time complexity of O(n). This algorithm is used to find the k smallest numbers in an array.

 * This algorithm is used to find the k smallest numbers in an array.
 */
public final class BFPRT {
    private BFPRT() {
    }

    /**
     * Returns the k smallest elements from the array using the BFPRT algorithm.
     *
     * @param arr the input array
     * @param k the number of smallest elements to return
     * @return an array containing the k smallest elements, or null if k is invalid
     */
    public static int[] getMinKNumsByBFPRT(int[] arr, int k) {
        if (k < 1 || k > arr.length) {
            return null;
        }
        int minKth = getMinKthByBFPRT(arr, k);
        int[] res = new int[k];
        int index = 0;
        for (int value : arr) {
            if (value < minKth) {
                res[index++] = value;
            }
        }
        for (; index != res.length; index++) {
            res[index] = minKth;
        }
        return res;
    }

    /**
     * Returns the k-th smallest element from the array using the BFPRT algorithm.
     *
     * @param arr the input array
     * @param k the rank of the smallest element to find
     * @return the k-th smallest element
     */
    public static int getMinKthByBFPRT(int[] arr, int k) {
        int[] copyArr = copyArray(arr);
        return bfprt(copyArr, 0, copyArr.length - 1, k - 1);
    }

    /**
     * Creates a copy of the input array.
     *
     * @param arr the input array
     * @return a copy of the array
     */
    public static int[] copyArray(int[] arr) {
        int[] copyArr = new int[arr.length];
        System.arraycopy(arr, 0, copyArr, 0, arr.length);
        return copyArr;
    }

    /**
     * BFPRT recursive method to find the k-th smallest element.
     *
     * @param arr the input array
     * @param begin the starting index