PHP中数组二分查找的实现

  • Z时代
  • 2024-01-10
  • 分类：综合

我最近一直在阅读和观看编程理论的讲座，这让我想起了我在大学学到的这个算法。二进制搜索数组是一种分治算法，它采用一个数组并通过将数组分成两半来搜索该数组中的值。算法是这样工作的。

  • 给定一个排序数组，找到中点。

  • 如果中点的值大于要搜索的值，则该值必须位于数组的前半部分。

  • 如果中点的值小于要搜索的值，则该值必须位于数组的前半部分。

  • 取有问题的数组的一半，并通过重新指向中点来重复第一步。

  • 重复此操作，直到数组的长度为 1 或 0。如果数组长度为 1，则这就是值。如果数组的长度为 0，则该值不在数组中。

有一些实现细节可以确保中间值是正确的，并避免从数组的末尾跑掉。

这是该算法在 PHP 中的实现。

/**
 * Use binary search to find a key of a value in an array.
 *
 * @param array $array
 *   The array to search for the value.
 * @param int $value
 *   A value to be searched.
 *
 * @return int|null
 *   Returns the key of the value in the array, or null if the value is not found.
 */
function binarySearch($array, $value) {
    // 将左指针设置为 0。
    $left = 0;
    // 将右指针设置为数组的长度 -1。
    $right = count($array) - 1;
 
    while ($left <= $right) {
      // 将初始中点设置为数组长度一半的向下舍入值。
      $midpoint = (int) floor(($left + $right) / 2);
 
      if ($array[$midpoint] < $value) {
        // 中点值小于该值。
        $left = $midpoint + 1;
      } elseif ($array[$midpoint] > $value) {
        // 中点值大于该值。
        $right = $midpoint - 1;
      } else {
        // 这是我们正在寻找的关键。
        return $midpoint;
      }
    }
    // 未找到该值。
    return NULL;
}

为了对这个算法运行一些测试，我运行了以下代码。所有这些都打印为真。

// 生成数组。
$array = range(0, 10);
 
// 遍历数组，搜索每个值。
foreach ($array as $key => $value) {
  echo var_export(binarySearch($array, $value) === $value, TRUE) . PHP_EOL;
}
 
// 搜索数组外的值。
echo var_export(binarySearch($array, -1) === NULL, TRUE) . PHP_EOL;
echo var_export(binarySearch($array, 11) === NULL, TRUE) . PHP_EOL;

这是一个简洁的小算法，非常适合搜索排序数据的数组，其中数组的键是连续的。比简单地遍历数组以查找值要高效得多。

以上是 PHP中数组二分查找的实现 的全部内容， 来源链接： utcz.com/z/335524.html

回到顶部