# 前言

藉由 LeetCode 磨練演算法

# 題目連結

Search Insert Position - LeetCode

# 解題思路

# 暴力解法

暴力解的話，跑一個 loop

• 當 target === $nums[$i] 時, $i 為答案
• 當 $i === 0 && $target < $nums[$i]，那代表 $target < $nums 中的最小數字，所以答案為 $i
• 當首次 target < $num[$i] 時，$i — 1 為答案
• 當跑完 loop 都沒有結果時，代表 $target > $nums 中的最大數字，所以答案為 $i + 1

時間複雜度為 O(n)，空間複雜度為 O(1)

# binary search

利用 binary search 來解題

先看過下面的 example code，再來看思路，比較對得上

在每一次的 binary search 中，藉由公式 $pivot = $left + ($right - $left) / 2 取得 $pivot，藉由比較 $pivot 與 $target 來得到 $target 會在 $pivot 的左側 or 右側，所以可以用更小的次數來求得答案

想了一陣子，歸納出一個邏輯

當 $left & $right & $pivot 重疊 或 $left 與 $right 相鄰，且 $pivot 與 $left or $right 任一重疊 時，勢必代表 找不到 $target

此時有兩種可能

• $target 比 $pivot 小：此時 若不存在時需 insert 的位置應為 $pivot 位置，這時會 $left 不動，而 $right = $pivot — 1 並終止 $left <= $right 的條件，取得 $left = $pivot 就是答案
• $target 比 $pivot 大：此時 若不存在時需 insert 的位置應為 $pivot 位置的右邊，這時會 $right 不動，而 $left = $pivot + 1 並終止 $left <= $right 的條件，$left = $pivot + 1剛好為答案

# 流程圖

假設 $target = 22，以下為求得 binary search 求得最後的 $left & $right 的流程

取得的 $left index 為 2，也是本題的答案

下面用一些假設來延伸解釋

注意看最後的兩個步驟，並且套用上面歸納出的邏輯

假如 $target 是 30，30 > $pivot，最終 $right 會往 $pivot 左邊移動，$left = $pivot，為解答

假如 $target 是 26，那 26 < $right，最終 $left 會往 $pivot 右邊移動，$left = $pivot + 1，為解答

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

# solution code

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function searchInsert($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;
        while ($left <= $right) {
            $pivot = intval($left + ($right - $left) / 2);

            if ($nums[$pivot] === $target) {
                return $pivot;
            } elseif ($nums[$pivot] > $target) {
                $right = $pivot - 1;
            } else {
                $left = $pivot + 1;
            }
        }

        return $left;
    }
}