Array sorting/searching technique in PHP

Question

Hi, In PHP I have an array let say $array = array(2, 1, 8, 3, 6, 0, 10, 10)and I want to get second largest value of that array. Which sorting/searching technique will be best & how could I use it?

Answer 1

Something like this?

$array = array(2, 1, 8, 3, 6, 0, 10, 10);
rsort($array);

echo $array[1]; // 10

this reverse sorts the array and then outputs the second element.

Edit: if you want the second highest unique value, just add an array_unique call:

$array = array(2, 1, 8, 3, 6, 0, 10, 10);
$array = array_unique($array);
rsort($array);

echo $array[1]; // 8

Answer 2

I'd just remove the duplicates from your array (using array_unique) and then use rsort (which uses Quicksort) with the SORT_NUMERIC flag to sort numerically from highest to lowest:

$array = array(2, 1, 8, 3, 6, 0, 10, 10);
$unique_array = array_unique($array);
rsort($unique_array, SORT_NUMERIC);
$second_highest = $unique_array[1];  // will be 8

The PHP manual has a comparison of sorting techniques.

Answer 3

you could use rsort, but it will do a lot of additional operations which are not needed (quick sort has O(logn) complexity). It might be a lot faster if you pass the array only in one pass like this (O(n)):

$largest=$array[0];
$secondLargest=null; //none present, by default
foreach($array as $value)
  if($value>$largest)
  {
    $secondLargest=$largest;
    $largest=$value;
  }

it will be significantly faster on large arrays, but it is only good when you want the first, second, maybe third largest element. In all other cases it would be more reasonable to sort the array and take the N'th largest element dynamically.