How to find the median of a very large array in php

In PHP, sometimes we need to process a very large array, such as finding the median. But for very large arrays, using traditional sorting methods will be very time-consuming and memory-consuming. So, is there a more efficient way to find the median of a very large array? This article will introduce an efficient solution method based on the fast selection algorithm.

1. Introduction to Quick Selection Algorithm

The quick selection algorithm is an improved algorithm based on the quick sort algorithm. Its main idea is to find items in an unordered array through rapid division. The kth smallest element. Its time complexity is O(n), which is more efficient than the time complexity of conventional sorting algorithm O(n log n).

The basic steps of the quick selection algorithm are as follows:

1. Select a pivot element pivot (usually the first element in the array);
2. Put the elements in the array The elements are divided into two parts: smaller than pivot and larger than pivot;
3. If the number of elements smaller than pivot is less than k, continue to search for the k-th element among elements larger than pivot;
4. If less than If the number of pivot elements is greater than or equal to k, then continue to search for the k-th element among elements smaller than pivot;
5. Repeat the above steps until the k-th element is found.
6. Find the median of a very large array

We now consider how to use the fast selection algorithm to find the median of a very large array. Suppose we have a very large array $nums$ and need to find its median. We first perform a quick division on $nums$, dividing the elements into two parts smaller than pivot and larger than pivot. If the pivot is exactly in the middle of the array, then it is the median. Otherwise, based on the location of the pivot, we can judge that the search should continue on the side where the pivot is located.

The following are the detailed algorithm steps:

1. First, we need to determine the position of the median mid. If the number of elements $n$ in the array is an odd number, the median is $nums[(n-1)/2]$; if the number of elements $n$ is an even number, the median is $(nums[n /2-1] nums[n/2])/2$.
2. Quickly divide the array $nums$ and record the pivot position $pos$.
3. Based on the positional relationship between pos and mid, determine whether the median is on the left or right side of the pivot. If $pos< mid$, then the median is between positions $[pos 1,n-1]$; if $pos>=mid$, then the median is between positions $[0,pos-1]$ between.
4. Repeat steps 2 and 3 until the median is found.

The following is the corresponding PHP code implementation:

function quickSelect($nums, $k) {
    $n = count($nums);
    $left = 0;
    $right = $n - 1;
    $mid = ($n - 1) / 2;

    while (true) {
        $pos = partition($nums, $left, $right);
        if ($pos == $mid) {
            if ($n % 2 == 0) {
                // 偶数个元素
                return ($nums[$pos] + $nums[$pos + 1]) / 2;
            } else {
                // 奇数个元素
                return $nums[$pos];
            }
        } elseif ($pos < $mid) {
            $left = $pos + 1;
        } else {
            $right = $pos - 1;
        }
    }
}

function partition(&$nums, $left, $right) {
    $pivot = $nums[$left];
    $i = $left;
    $j = $right;

    while ($i < $j) {
        while ($i < $j && $nums[$j] >= $pivot) {
            $j--;
        }
        while ($i < $j && $nums[$i] <= $pivot) {
            $i++;
        }
        if ($i < $j) {
            $temp = $nums[$i];
            $nums[$i] = $nums[$j];
            $nums[$j] = $temp;
        }
    }

    // 将pivot元素放到正确的位置
    $nums[$left] = $nums[$i];
    $nums[$i] = $pivot;

    return $i;
}

// 测试示例
$nums = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
echo quickSelect($nums, 5); // 输出5（因为5在数组中的中间位置）

3. Summary

For very large arrays, using the traditional sorting method will bring very High time and space complexity. By using the fast selection algorithm to find the kth smallest element, we can complete the operation within O(n) time complexity, thereby achieving an efficient solution to the median of a very large array. It should be noted that in actual use, we also need to perform appropriate optimization according to different needs, such as pruning, etc.

The above is the detailed content of How to find the median of a very large array in php. For more information, please follow other related articles on the PHP Chinese website!