使用PHP描述顺序查找和二分查找(也叫做折半查找)算法,顺序查找必须考虑效率,对象可以是一个有序数组
2023-06-11 08:44
PHP
119
0
0
0
标题录入
封面图
使用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),因为每次查找都将数组规模减半。因此,对于大型有序数组来说,二分查找通常比顺序查找更高效。
上一篇:
php 二维数组排序
下一篇:
PHP操作文件的常用函数?
标题录入,一次不能超过6条
孤独与无聊的定义
T:0.006329s,M:248.16 KB
返回顶部
留言
留言
评论