PHP数组特定元素查找的算法效率比较

PHP 数组元素查找算法效率比较：线性搜索：无序数组中效率为 O(n)；二分搜索（有序数组）：时间复杂度为 O(log n)；散列表：时间复杂度始终为 O(1)，无论数组类型。

PHP 数组特定元素查找的算法效率比较

在 PHP 中查找数组中的特定元素是常见的任务，有多种算法可用于此目的。本文将比较三种最常见的算法的效率：

1. 线性搜索

function linearSearch($arr, $target) {
  for ($i = 0; $i < count($arr); $i++) {
    if ($arr[$i] === $target) {
      return $i;
    }
  }

  return -1;
}

2. 二分搜索（数组必须是有序的）

function binarySearch($arr, $target) {
  $left = 0;
  $right = count($arr) - 1;

  while ($left <= $right) {
    $mid = floor(($left + $right) / 2);

    if ($arr[$mid] === $target) {
      return $mid;
    } else if ($arr[$mid] < $target) {
      $left = $mid + 1;
    } else {
      $right = $mid - 1;
    }
  }

  return -1;
}

3. 散列表

散列表通过使用键值对来存储数据，可以显著提高查找速度。

function hashTableSearch($arr, $target) {
  $lookupTable = [];

  for ($i = 0; $i < count($arr); $i++) {
    $lookupTable[$arr[$i]] = true;
  }

  if (isset($lookupTable[$target])) {
    return true;
  } else {
    return false;
  }
}

实战案例

我们使用不同的数组大小进行测试，包含随机元素的无序数组和有序数组。结果如下：

结论

二分搜索在有序数组中表现最佳，时间复杂度为 O(log n)，而散列表在所有情况下效率最高，时间复杂度始终为 O(1)。