搜尋演算法

了解 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中文網其他相關文章！