使用PHP描述顺序查找和二分查找（也叫做折半查找）算法，顺序查找必须考虑效率，对象可以是一个有序数组

封面图 • 2023-06-11 • PHP

当给定一个对象（可以是有序数组）和一个目标值时，顺序查找和二分查找（折半查找）是两种常见的搜索算法。下面我会分别描述这两种算法的实现方法。

顺序查找（Sequential Search）：
顺序查找是一种简单直接的搜索算法，它逐个检查给定对象中的元素，直到找到目标值或遍历完所有元素。以下是顺序查找的实现示例：
php
```
<?php

function sequentialSearch($array, $target)
{
    $length = count($array);

for ($i = 0; $i < $length; $i++) {
        if ($array[$i] == $target) {
            return $i; // 返回目标值在数组中的索引
        }
    }

return -1; // 目标值不存在
}

// 示例使用
$array = [2, 5, 8, 12, 16, 23, 38, 56];
$target = 23;

$result = sequentialSearch($array, $target);

if ($result != -1) {
    echo "目标值 {$target} 在数组中的索引为 {$result}";
} else {
    echo "目标值 {$target} 不存在于数组中";
}

?>
```
在上述示例中，sequentialSearch函数接收一个数组$array和目标值$target作为参数。它使用for循环遍历数组中的每个元素，检查是否与目标值匹配。如果找到目标值，函数将返回目标值在数组中的索引；否则，返回-1表示目标值不存在于数组中。

二分查找（Binary Search）：
二分查找是一种高效的搜索算法，适用于有序数组。它通过将数组划分为两半并与目标值进行比较，然后根据比较结果确定目标值在哪一半中，并继续在该半中进行查找，以此类推，直到找到目标值或确定不存在。以下是二分查找的实现示例：
php
```
<?php

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

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

if ($array[$mid] == $target) {
            return $mid; // 返回目标值在数组中的索引
        }

if ($array[$mid] < $target) {
            $left = $mid + 1; // 在右半部分查找
        } else {
            $right = $mid - 1; // 在左半部分查找
        }
    }

return -1; // 目标值不存在
}

// 示例使用
$array = [2, 5, 8, 12, 16, 23, 38, 56];
$target = 23;

$result = binarySearch($array, $target);

if ($result != -1) {
    echo "目标值 {$target} 在数组中的索引为 {$result}";
} else {
    echo "目标值 {$target} 不存在于数组中";
}

?>
```
在上述示例中，binarySearch函数接收一个有序数组$array和目标值$target作为参数。它使用while循环来进行二分查找。在每次迭代中，将数组划分为左半部分和右半部分，然后根据目标值与中间元素的比较结果，确定继续查找的半部分。如果找到目标值，函数将返回目标值在数组中的索引；否则，返回-1表示目标值不存在于数组中。

无论是顺序查找还是二分查找，其效率与输入规模有关。顺序查找的时间复杂度为O(n)，其中n是数组的大小。而二分查找的时间复杂度为O(log n)，因为每次查找都将数组规模减半。因此，对于大型有序数组来说，二分查找通常比顺序查找更高效。