Learn/PHP/12. Sorting and searching
Lesson 12 of 15
Sign in

PHP, lesson 12

Sorting and searching

PHP has a whole family of sort functions. They all sort in place (they change the array you pass and return true), and since PHP 8 they are all stable: elements that compare equal keep their original order. The differences are what they sort by and whether they keep the keys.

FunctionSorts byKeeps keys?Order
sortvaluenolow to high
rsortvaluenohigh to low
asortvalueyeslow to high
arsort

2 exercises to try what you just read.

Exercise 1

Leaderboard

Press Ctrl Enter or Check to test your code.

Exercise 2

Shelf finder

Press Ctrl Enter or Check to test your code.

value
yes
high to low
ksortkeyyeslow to high
krsortkeyyeshigh to low
usortvaluenoyour function
uasortvalueyesyour function
uksortkeyyesyour function

For a list, sort() is usually what you want. For an associative array such as ["ana" => 70, "ben" => 50], use asort() or arsort() to sort by value while keeping each name attached to its score, and ksort() to sort by name.

Custom ordering with usort

usort() takes a comparison function. It receives two elements and returns a negative number if the first should come first, a positive number if the second should, and 0 if they're equal. The spaceship operator <=> returns exactly that:

Swap $a and $b on the right side to reverse the order.

Sorting by several things

<=> also compares arrays element by element. That makes multi-key sorting a one-liner: build an array of keys for each side. To make one key descending, swap which side it comes from:

Read it as: compare $b's score with $a's score (descending), and if they tie, compare $a's name with $b's name (ascending).

String comparison with <=> is byte-based, so uppercase letters sort before lowercase. Use strcasecmp() or strnatcmp() in your comparison when that matters.

Searching

in_array($needle, $array, true) answers "is it there?", and array_search() returns the key where the value was found, or false. Because the key can be 0, always test the result with !== false.

Both look at every element in turn, a linear search. For a big, sorted list, binary search is much faster: check the middle element, throw away the half that can't hold the target, and repeat. A million elements take about twenty steps.

PHP has no built-in binary search for arrays, so this small function is worth knowing. Watch the boundaries: $low <= $high (not <) and the + 1 / - 1 updates are what stop it from looping forever or skipping the last candidate.

If you search the same data many times by exact value, an even faster option is to flip it into a map with array_flip() and use isset(); lesson 13 shows how.

Further reading

  • Sorting arrays
  • usort()
  • Comparison operators and <=>
  • array_search()

The first line is n, the number of players. Each of the next n lines holds a name and a score. Print the players by score from highest to lowest; equal scores appear in alphabetical order. Each output line is rank. name score, where rank starts at 1.

Sample input:

Sample output:

A warehouse keeps its item codes in a sorted list. The first input line holds the codes (whole numbers in ascending order, separated by spaces). Each following line is a code to look up. Write binarySearch() and print the zero-based position of each code, or missing.

Sample input:

Sample output:

<?php

$words = ["banana", "fig", "cherry"];
usort($words, fn($a, $b) => strlen($a) <=> strlen($b));
// ["fig", "banana", "cherry"]: equal lengths keep their order (stable)
<?php

$players = [["ana", 70], ["ben", 50], ["cleo", 70]];

// score high to low, then name A to Z
usort($players, fn($a, $b) => [$b[1], $a[0]] <=> [$a[1], $b[0]]);
<?php

function binarySearch(array $sorted, int $target): int
{
    $low = 0;
    $high = count($sorted) - 1;
    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);
        if ($sorted[$mid] === $target) {
            return $mid;
        }
        if ($sorted[$mid] < $target) {
            $low = $mid + 1;    // target is in the right half
        } else {
            $high = $mid - 1;   // target is in the left half
        }
    }
    return -1;                  // not found
}
4
cleo 50
ana 70
ben 50
dev 90
1. dev 90
2. ana 70
3. ben 50
4. cleo 50
3 8 15 23 42 57
23
4
3
57
3
missing
0
5