php二分查找邊界處理

PHP
小樊
81
2024-10-17 15:42:56

在PHP中實(shí)現(xiàn)二分查找算法時(shí)，需要處理邊界條件。二分查找要求輸入的數(shù)組是有序的。以下是處理邊界條件的步驟：

  1. 確定數(shù)組的起始索引（low）和結(jié)束索引（high）。初始時(shí)，low為數(shù)組的第一個(gè)元素的索引（0），high為數(shù)組的最后一個(gè)元素的索引（count($array) - 1）。

  2. 當(dāng)low <= high時(shí)，執(zhí)行循環(huán)： a. 計(jì)算中間索引（mid）：mid = (low + high) / 2。 b. 檢查中間元素是否等于目標(biāo)值：

    • 如果中間元素等于目標(biāo)值，則返回mid。
    • 如果中間元素小于目標(biāo)值，則更新low為mid + 1，表示目標(biāo)值在數(shù)組的右半部分。
    • 如果中間元素大于目標(biāo)值，則更新high為mid - 1，表示目標(biāo)值在數(shù)組的左半部分。

  3. 如果循環(huán)結(jié)束還沒有找到目標(biāo)值，則返回-1，表示目標(biāo)值不在數(shù)組中。

以下是一個(gè)PHP實(shí)現(xiàn)的二分查找示例：

function binarySearch($array, $target)
{
    $low = 0;
    $high = count($array) - 1;

    while ($low <= $high) {
        $mid = (int)(($low + $high) / 2);

        if ($array[$mid] == $target) {
            return $mid;
        } elseif ($array[$mid] < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }

    return -1;
}

使用這個(gè)函數(shù)，你可以在有序數(shù)組中高效地查找目標(biāo)值。

0 踩