Method bfprt

src/main/java/com/thealgorithms/others/BFPRT.java:71–84

BFPRT recursive method to find the k-th smallest element. @param arr the input array @param begin the starting index @param end the ending index @param i the index of the desired smallest element @return the k-th smallest element

(int[] arr, int begin, int end, int i)

     * @return the k-th smallest element
     */
    public static int bfprt(int[] arr, int begin, int end, int i) {
        if (begin == end) {
            return arr[begin];
        }
        int pivot = medianOfMedians(arr, begin, end);
        int[] pivotRange = partition(arr, begin, end, pivot);
        if (i >= pivotRange[0] && i <= pivotRange[1]) {
            return arr[i];
        } else if (i < pivotRange[0]) {
            return bfprt(arr, begin, pivotRange[0] - 1, i);
        } else {
            return bfprt(arr, pivotRange[1] + 1, end, i);
        }
    }

    /**
     * Finds the median of medians as the pivot element.