PHP 有序陣列插入元素並保持原序演算法

問題情境

已有一個由小到大排序的數值陣列，需插入新數值並維持排序順序，且不重新排序整個陣列（O(n) 複雜度）。

解法：二分搜尋定位 + array_splice 插入

利用 PHP 內建 `array_splice` 在指定位置插入，避免手動位移元素。

/**
 * 於已排序陣列插入數值，保持升序
 * @param array $arr  已排序陣列（傳址修改）
 * @param int|float $val  待插入數值
 * @return array  插入後的陣列
 */
function sortedInsert(array &$arr, $val): array {
    $left = 0;
    $right = count($arr) - 1;
    $pos = count($arr); // 預設插入尾端

    // 二分搜尋找到第一個 >= $val 的位置
    while ($left <= $right) {
        $mid = (($left + $right) >> 1);
        if ($arr[$mid] >= $val) {
            $pos = $mid;
            $right = $mid - 1;
        } else {
            $left = $mid + 1;
        }
    }

    array_splice($arr, $pos, 0, [$val]);
    return $arr;
}

// 測試
$data = [10, 20, 30, 40, 50];
sortedInsert($data, 35); // [10,20,30,35,40,50]
sortedInsert($data, 5);  // [5,10,20,30,35,40,50]
sortedInsert($data, 55); // [5,10,20,30,35,40,50,55]
print_r($data);

效能分析

進階：支援重複值與自定義比較

function sortedInsertEx(array &$arr, $val, callable $cmp = null): array {
    $cmp = $cmp ?? fn($a, $b) => $a <=> $b; // PHP 7+ 太空船運算子
    $pos = count($arr);
    $left = 0;
    $right = $pos - 1;
    while ($left <= $right) {
        $mid = (($left + $right) >> 1);
        if ($cmp($arr[$mid], $val) >= 0) {
            $pos = $mid;
            $right = $mid - 1;
        } else {
            $left = $mid + 1;
        }
    }
    array_splice($arr, $pos, 0, [$val]);
    return $arr;
}

// 物件陣列依屬性排序
$users = [
    ['id'=>1, 'score'=>80],
    ['id'=>2, 'score'=>90],
];
sortedInsertEx($users, ['id'=>3, 'score'=>85], fn($a,$b)=>$a['score']<=>$b['score']);
// 結果：80, 85, 90

總結

• 單筆插入維持有序：二分搜尋定位 + array_splice 是最佳平衡點。
• 批次大量插入：收集所有新值，合併後 sort() 一次完成更快。
• PHP 8.1+ 可用 array_is_list() 檢查陣列為列表型，避免關聯陣列誤用。