PHP Algorithm Collection: Fibonacci, File Scanning, Binary Search, Sorting, and a LeetCode Problem

Introduction: The author argues that PHP developers often overlook algorithmic knowledge, yet many interview processes require implementations of basic algorithms such as bubble sort, and provides a collection of useful PHP algorithm examples.

Completed algorithms:

Fibonacci sequence

Directory scanning

Binary search

Bubble sort

Quick sort

LeetCode problem #1 (Two Sum)

TODO algorithms (to be added later):

Heap sort

Selection sort

Linked list reversal

Dynamic programming

Code implementation:

<?php
class Algorithmic {
    /***
     * Recursive Fibonacci, may cause stack overflow for large n
     */
    function fib($n) {
        if ($n < 2) {
            return 1;
        } else {
            return $this->fib($n - 1) + $this->fib($n - 2);
        }
    }
    /***
     * Iterative Fibonacci using an array (higher space complexity)
     */
    function fib2($n) {
        if ($n < 2) {
            return 1;
        } else {
            $arr = [1, 1];
            for ($i = 2; $i <= $n; $i++) {
                $arr[$i] = $arr[$i - 1] + $arr[$i - 2];
            }
        }
        return $arr[$n];
    }
    /***
     * Iterative Fibonacci using two variables (lower space complexity)
     */
    function fib3($n) {
        if ($n < 2) {
            return 1;
        } else {
            $last = 1;      // f(n-1)
            $lastLast = 1;  // f(n-2)
            for ($i = 2; $i <= $n; $i++) {
                $current = $last + $lastLast;
                $lastLast = $last;
                $last = $current;
            }
            return $current;
        }
    }
    /***
     * Scan a directory and return a nested file list
     */
    function scanFile($dir) {
        $fileList = [];
        if (is_dir($dir)) {
            $dh = opendir($dir);
            while ($file = readdir($dh)) {
                if ($file == '.' || $file == '..') continue;
                $newDir = $dir . '/' . $file;
                if (is_dir($newDir)) {
                    $fileList[][$file] = $this->scanFile($newDir);
                } else {
                    $fileList[] = $file;
                }
            }
            closedir($dh);
        }
        return $fileList;
    }
    /***
     * Binary search in a sorted array
     */
    function binarySort($arr, $target) {
        if (!is_array($arr) || count($arr) < 2) {
            return $arr;
        }
        $len = count($arr);
        $start = 0;
        $end = $len - 1;
        while ($start <= $end) {
            $middle = floor(($start + $end) / 2);
            if ($arr[$middle] == $target) {
                return $middle;
            } elseif ($arr[$middle] < $target) {
                $start = $middle + 1;
            } else {
                $end = $middle - 1;
            }
        }
        return false;
    }
    /***
     * Bubble sort
     */
    function bubbleSort($arr) {
        for ($i = count($arr) - 1; $i > 0; $i--) {
            for ($j = 0; $j < $i; $j++) {
                if ($arr[$j+1] < $arr[$j]) {
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j+1];
                    $arr[$j+1] = $temp;
                }
            }
        }
        return $arr;
    }
    /***
     * Quick sort
     */
    function quickSort($arr) {
        if (!is_array($arr) || count($arr) < 2) {
            return $arr;
        }
        $base = $arr[0];
        $left = [];
        $right = [];
        for ($i = 1; $i <= count($arr) - 1; $i++) {
            if ($arr[$i] < $base) {
                $left[] = $arr[$i];
            } else {
                $right[] = $arr[$i];
            }
        }
        return array_merge(array_merge($this->quickSort($left), [$base]), $this->quickSort($right));
    }
    /***
     * Two Sum – LeetCode problem #1
     */
    function twoSum($arr, $sum = 8) {
        $tempArr = [];
        foreach ($arr as $k => $v) {
            if (isset($tempArr[$v])) {
                return [$k, $tempArr[$v]];
            }
            $tempArr[$sum - $v] = $k;
        }
        return [];
    }
}
$algorithmic = new Algorithmic();
var_dump($algorithmic->quickSort([14,5,13,114,4,3,167,87,14]));
?>

The article ends with a call to view the original WeChat article for more details.