当前位置：首页 > article >正文

PHP顺序查找和二分查找（也叫做折半查找）算法

article 2024/11/23 2:15:04

顺序查找（线性查找）

顺序查找是一种简单直观的查找算法，从数组的第一个元素开始，依次比较每个元素，直到找到目标元素或数组结束。

<?php
function linearSearch($array, $target) {
    $length = count($array);
    for ($i = 0; $i < $length; $i++) {
        if ($array[$i] == $target) {
            return $i; // 返回目标元素的索引
        }
    }
    return -1; // 如果未找到目标元素，返回-1
}

// 示例
$array = [2, 4, 6, 8, 10, 12, 14];
$target = 8;
$result = linearSearch($array, $target);

if ($result != -1) {
    echo "元素 $target 在数组中的索引为: $result\n";
} else {
    echo "元素 $target 不在数组中\n";
}
?>

二分查找（折半查找）

二分查找是一种高效的查找算法，要求数组必须是有序的。它通过不断将查找范围缩小一半，从而快速找到目标元素。

<?php
function binarySearch($array, $target) {
    $left = 0;
    $right = count($array) - 1;

    while ($left <= $right) {
        $mid = intdiv($left + $right, 2); // 计算中间索引

        if ($array[$mid] == $target) {
            return $mid; // 返回目标元素的索引
        } elseif ($array[$mid] < $target) {
            $left = $mid + 1; // 目标元素在右半部分
        } else {
            $right = $mid - 1; // 目标元素在左半部分
        }
    }
    return -1; // 如果未找到目标元素，返回-1
}

// 示例
$array = [2, 4, 6, 8, 10, 12, 14];
$target = 10;
$result = binarySearch($array, $target);

if ($result != -1) {
    echo "元素 $target 在数组中的索引为: $result\n";
} else {
    echo "元素 $target 不在数组中\n";
}
?>