前言

今天要解的題目是 Search Insert Position（搜尋插入位置）。

題目要求我們在一個已經排序好的陣列中找到目標數字的位置。

如果找到目標數字，就返回它的索引位置；如果找不到，則返回它應該插入的位置，保持陣列的排序性。

這道題的難點是時間複雜度必須是 O(log n)，這意味著我們需要使用二分搜尋法。
那就一起來看看怎麼解決這個問題吧！

英文題目 Search Insert Position

難度：Easy

題目描述：

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

給定一個已經排序好的、無重複元素的整數陣列 nums 和一個目標值 target，請返回目標值在陣列中的索引位置。如果找不到目標值，則返回它應該被插入的位置以保持陣列的有序性。

你必須實現一個時間複雜度為 O(log n) 的演算法。

範例 1：

輸入： nums = [1, 3, 5, 6]，target = 5

輸出： 2

範例 2：

輸入： nums = [1, 3, 5, 6]，target = 2

輸出： 1

範例 3：

輸入： nums = [1, 3, 5, 6]，target = 7

輸出： 4

思路

這道題的核心是二分搜尋法。我們知道，對於已排序的陣列，二分搜尋是解決搜尋問題的最佳方法。二分搜尋的原理是每次將搜尋範圍縮小一半，這樣可以大幅減少搜尋的時間。

詳細步驟

1. 初始化左右邊界：

   • 我們設置兩個指針，left 和 right，分別代表陣列的左右邊界。

2. 二分搜尋：

   • 我們計算中間位置 mid，然後將 mid 的值與目標值 target 進行比較。
   • 如果 nums[mid] 恰好等於 target，那麼我們直接返回 mid 這個索引。
   • 如果 nums[mid] 小於 target，那麼說明目標值在右半部分，我們將 left 更新為 mid + 1。
   • 如果 nums[mid] 大於 target，那麼目標值在左半部分，我們將 right 更新為 mid - 1。

3. 返回插入位置：

   • 如果最終沒有找到目標值，left 的位置就是目標值應該插入的位置。這是因為在每次縮小搜尋範圍後，left 會逐步逼近目標值的插入位置。

實作

function searchInsert(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid; // 找到目標值，返回索引
        } else if (nums[mid] < target) {
            left = mid + 1; // 在右半部分搜尋
        } else {
            right = mid - 1; // 在左半部分搜尋
        }
    }

    // 沒有找到目標值，返回應插入的位置
    return left;
}

解題心法

1. 為什麼要用二分搜尋？

   • 題目要求時間複雜度為 O(log n)，這恰好是二分搜尋的特性。二分搜尋每次將搜尋範圍減半，因此能夠在 O(log n) 的時間內解決問題。

2. 左右邊界的更新：

   • 當目標值比中間值大時，說明目標值在右半部分，將 left 更新為 mid + 1；
   • 當目標值比中間值小時，說明目標值在左半部分，將 right 更新為 mid - 1。
   • 這樣不斷縮小範圍，直到找到目標值，或者當 left > right 時，說明目標值不在陣列中。

3. 返回插入位置：

   • 如果目標值不在陣列中，那麼最終 left 指針的位置就是目標值應該插入的位置，因為此時 left 代表的是比目標值稍大的元素的位置。

為什麼這樣處理？

這種方法利用了二分搜尋的高效性，能夠在 O(log n) 的時間內找到目標值或確定插入位置。每次我們只需比較中間值，然後將搜尋範圍縮小一半，這使得演算法非常高效。對於大規模數據集，這種方法尤為適用。

本次要點：

• 二分搜尋法：用來高效地處理排序陣列的搜尋問題。
• 左右邊界更新：每次比較中間值後，決定是往左邊還是右邊繼續搜尋。
• 插入位置：當找不到目標值時，left 的位置就是目標值應插入的位置。

這道題是不是很經典呢？二分搜尋法是一個非常強大的工具，當你面對排序陣列的搜尋問題時，記得首先考慮這種方法。下次我們再來一起挑戰更多有趣的題目吧！🌟