# 前言

藉由 LeetCode 磨練演算法

# 題目連結

Find First and Last Position of Element in Sorted Array - LeetCode

# 解題思路

# 暴力解

loop $nums

若有找到 $target

• 則第一次出現位置為 $left
• 最後一次出現位置為 $right

若都無找到 $target，return [-1, -1]

複雜度：

• 時間複雜度為 O(N)
• 空間複雜度為 O(1)

# binary search

透過兩次 binary search 分別找到 $left & $right

請配合參考下面的 solution code 幫助理解

要找出 $left，所以透過不斷的移動 $right 來縮小範圍

假如 $left 的初始位置就等同 $target，那最後 $left 與 $right 重疊，解除 $left < $right 的條件，得到 $left 為 $target 的最左側

假如 $target 不在 $nums 之內，那最終就是兩個結果。假設 $nums 最大值為 m，最小值為 n

• 當 $target 初始值就 < $nums 的最小值時，最終 $left 會跳出 $nums 的範圍
• 當 $target 初始值就 > $nums 的最大值時，最終 $right 會跳出 $nums 的範圍，而 $nums[$left] 會 !== $target
• 當 n < $target < m，但 $target 不存在於 $nums 時，這時最終取得的 $nums[$left] 會 !== $target

使用 while ($left < $right) 是因為當 $left 初始值就 === $target 時，最終勢必與 $right 重疊，若使用 while ($left <= $right) 會造成無限迴圈

尋找 $left 的 pivot 使用 intval($left + ($right - $left) / 2) 是因為當 $left 與 $right 相鄰時，必須要讓 $pivot 是偏左的，否則 if ($pValue >= $target) 的條件會造成無限迴圈

尋找 $right 的 pivot 使用 intval($left + ($right - $left) / 2 + 1) 是因為當 $left 與 $right 相鄰時，必須要讓 $pivot 是偏右的，否則 if ($pValue <= $target) 的條件會造成無限迴圈

當尋找 $left 且情境如下時，$pivot 必須使用 intval($left + ($right - $left) / 2)

當尋找 $right 且情境如下時，$pivot 必須使用 intval($left + ($right - $left) / 2 + 1)

透過兩次 binary search 便可以求得解答

複雜度：

• 時間複雜度為 O(logN)
• 空間複雜度為 O(1)

# solution code

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function searchRange($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;

        while ($left < $right) {
            $pivot = intval($left + ($right - $left) / 2);
            $pValue = $nums[$pivot];

            if ($pValue >= $target) {
                $right = $pivot;
            } else {
                $left = $pivot + 1;
            }
        }


        if ($nums[$left] !== $target || !isset($nums[$left])) {
            return [-1, -1];
        }

        $result[] = $left;

        $right = count($nums) - 1;

        while ($left < $right) {
            $pivot = intval($left + ($right - $left) / 2 + 1);
            $pValue = $nums[$pivot];

            if ($pValue <= $target) {
                $left = $pivot;
            } else {
                $right = $pivot - 1;
            }
        }

        $result[] = $right;

        return $result;
    }
}