搜索算法

了解 PHP 中的二分查找

二分搜索是一种在排序数组中查找元素的更有效的算法。它的工作原理是反复将搜索间隔分成两半。以下是二元搜索函数的详细分解：

function binarySearch(array $arr, float|int $x)
{
    $low = 0;
    $high = count($arr)-1;
    // $midIndex = (int) ($low + ($high - $low)/2);
    $i = 0;
    while($low <= $high){
        $i++;
        $midIndex = (int) ($low + (($high - $low)/2)); //the same as  intdiv($low + $high, 2);

        if($arr[$midIndex] == $x){
            return "The number {$x} was found in index {$midIndex} of the array. The number of iteration was {$i}";
        }elseif($x > $arr[$midIndex]){
            $low = $midIndex +1;
            echo $low."\n";
        }else{
            $high = $midIndex - 1;
        }
    }

return "The number {$x} was not found in the array";


}

echo binarySearch([1,2,3,4,5,6,7,8,9,10,44,45,46,47,48,49,50], 45)

函数binarySearch接受两个参数：

1. $arr：已排序的整数数组。
2. $x：要查找的数字，可以是浮点数，也可以是整数。
3. $low 被初始化为数组的第一个索引。
4. $high 被初始化为数组的最后一个索引。
5. $i 是一个计数器，用于跟踪迭代次数。
6. 只要搜索间隔有效（$low 小于或等于 $high），while 循环就会运行。
7. $midIndex 计算为当前区间的中间索引。
8. 如果中间元素等于$x，函数返回索引和迭代次数。
9. 如果$x大于中间元素，则将$low调整为midIndex + 1（将搜索范围缩小到上半部分）。
10. 如果$x小于中间元素，则将$high调整为midIndex - 1（将搜索范围缩小到下半部分）。

了解 PHP 中的线性搜索

线性搜索是用于查找数组中特定元素的最简单的搜索算法之一。让我们分解一下 PHP 中的 LinearSearch 函数。

function linearSearch(array $arr, float|int $x)
{
    for($i=0; $i < count($arr); $i++){
        if($x === $arr[$i]){
            return "The number {$x} was found in index {$i} of the array\n";
        }
    }

    return "The number {$x} was not found in the array\n";
}

echo linearSearch([1,5,6,3,4,11,3,2], 4);

函数 LinearSearch 接受两个参数：

1. $arr：整数数组。
2. $x：要查找的数字，可以是浮点数，也可以是整数。
3. for 循环迭代数组的每个元素。 count($arr) 函数返回数组中元素的数量。
4. 在循环内，代码检查当前元素 ($arr[$i]) 是否等于 $x。如果找到匹配项，它会返回一条消息，指示找到该号码的索引。
5. 如果循环完成时没有找到该数字，该函数将返回一条消息，指示在数组中未找到该数字。
6. 线性搜索简单且易于实现。它顺序检查数组的每个元素，直到找到所需的元素或到达数组末尾。这种方法很简单，但对于大型数组来说效率较低，因为它的时间复杂度为 O(n)。

以上是搜索算法的详细内容。更多信息请关注PHP中文网其他相关文章！