PHP数组特定元素查找的算法效率比较-php教程-PHP中文网

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

PHPz

发布： 2024-05-01 11:03:01

原创

732人浏览过

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

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

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

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

1. 线性搜索

立即学习“PHP免费学习笔记（深入）”；

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;
  }
}

登录后复制

实战案例

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