Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：35. Search Insert Position（搜索插入位置）

二分查找的經典應用與邊界處理技巧

luk 收錄於 Leetcode
 約 1400 字 預計閱讀 7 分鐘 

題目描述

給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。

請必須使用時間複雜度為 O(log n) 的演算法。

範例

範例 1：

輸入：nums = [1,3,5,6], target = 5
輸出：2
解釋：5 在數組中，索引為 2

範例 2：

輸入：nums = [1,3,5,6], target = 2
輸出：1
解釋：2 不在數組中，應該插入到索引 1 的位置

範例 3：

輸入：nums = [1,3,5,6], target = 7
輸出：4
解釋：7 不在數組中，應該插入到數組末尾

範例 4：

輸入：nums = [1,3,5,6], target = 0
輸出：0
解釋：0 不在數組中，應該插入到數組開頭

限制條件

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 為無重複元素的升序排列數組
  • -10^4 <= target <= 10^4

核心概念理解

1. 問題本質

這題本質上是二分查找的變體：

  • 如果找到目標值，返回其位置
  • 如果找不到，返回「第一個大於目標值的位置」
  • 這個位置就是目標值應該插入的位置

2. 為什麼必須用 O(log n)？

  • 數組已排序 → 提示使用二分查找
  • O(log n) 要求 → 明確要求二分查找
  • 線性搜索 O(n) 不符合要求

3. 插入位置的定義 

對於數組 [1, 3, 5, 6]：
- 插入 0：位置 0 → [0, 1, 3, 5, 6]
- 插入 2：位置 1 → [1, 2, 3, 5, 6]
- 插入 4：位置 2 → [1, 3, 4, 5, 6]
- 插入 7：位置 4 → [1, 3, 5, 6, 7]

關鍵理解：插入位置 = 第一個 ≥ target 的元素的位置

解法一：標準二分查找（推薦）

思路

使用標準的二分查找模板，但需要特別處理「找不到」的情況。

程式碼實現 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        # 當 left > right 時，left 就是插入位置
        return left

為什麼返回 left？ 

當循環結束時：
- right < left
- right 指向最後一個 < target 的位置
- left 指向第一個 > target 的位置
- 所以 left 就是插入位置！

示例：[1,3,5,6] 找 2
最後：right = 0 (指向1), left = 1 (指向3)
插入位置就是 1

執行過程視覺化 

範例：nums = [1,3,5,6], target = 2

初始狀態：
[1, 3, 5, 6]
 ↑        ↑
left    right
      ↑
     mid

步驟 1：nums[2] = 5 > 2，向左搜索
[1, 3, 5, 6]
 ↑  ↑
left right
 ↑
mid

步驟 2：nums[0] = 1 < 2，向右搜索
[1, 3, 5, 6]
    ↑  ↑
   left right

步驟 3：nums[1] = 3 > 2，向左搜索
[1, 3, 5, 6]
 ↑  ↑
right left

結束：left = 1，這就是插入位置

複雜度分析

  • 時間複雜度：O(log n)，標準二分查找
  • 空間複雜度：O(1)，只用常數空間

解法二：尋找左邊界的二分查找

思路

將問題轉化為：尋找第一個 ≥ target 的位置。

重要澄清：這不是從第一個元素開始線性搜索！而是使用二分查找的變體，仍然保持 O(log n) 的時間複雜度。

錯誤理解 vs 正確理解 

# ❌ 錯誤理解：線性搜索 O(n)
def findFirstGreaterOrEqual_Wrong(nums, target):
    for i in range(len(nums)):
        if nums[i] >= target:
            return i
    return len(nums)

# ✅ 正確：二分查找變體 O(log n)
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] < target:
                left = mid + 1
            else:
                # nums[mid] >= target
                # 可能是答案，但要繼續往左找看有沒有更早的
                right = mid
        
        return left

為什麼這還是 O(log n)？

關鍵在於每次都將搜索範圍減半：

例子：在 [1,3,5,6,8,10,12] 中找插入 7 的位置

步驟 1：
[1, 3, 5, 6, 8, 10, 12]
 ↑           ↑        ↑
left        mid     right
nums[3]=6 < 7，往右半部搜索

步驟 2：
[1, 3, 5, 6, 8, 10, 12]
             ↑   ↑    ↑
           left mid  right
nums[5]=10 >= 7，往左半部搜索（但保留 mid）

步驟 3：
[1, 3, 5, 6, 8, 10, 12]
             ↑ ↑ ↑
           left mid/right
nums[4]=8 >= 7，繼續往左

最終：left = right = 4，這是第一個 >= 7 的位置

兩種二分查找模板的比較

特點標準二分（解法一）左邊界二分（解法二）
right 初始值len(nums) - 1len(nums)
循環條件left <= rightleft < right
找到目標時立即返回繼續往左找
right 更新right = mid - 1right = mid
搜索範圍[left, right][left, right)
終止條件left > rightleft == right

時間複雜度分析 

初始範圍：n 個元素
第 1 次迭代後：n/2 個元素
第 2 次迭代後：n/4 個元素
第 3 次迭代後：n/8 個元素
...
第 k 次迭代後：n/2^k 個元素

當 n/2^k = 1 時結束
k = log₂(n)

所以時間複雜度是 O(log n)

為什麼這樣設計？ 

# 左邊界二分的精髓：
# 1. 找到 >= target 的元素時不立即返回
# 2. 而是繼續在左半部分查找，看有沒有更早的
# 3. 最終收斂到第一個 >= target 的位置
# 4. 能正確處理插入到數組末尾的情況

解法三：Python 內建方法

使用 bisect 模組 

import bisect

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

bisect 模組說明 

# bisect_left: 返回插入位置（相同元素的左邊）
# bisect_right: 返回插入位置（相同元素的右邊）

nums = [1, 3, 3, 3, 5]
bisect_left(nums, 3)  # 返回 1
bisect_right(nums, 3) # 返回 4

常見錯誤與陷阱

錯誤 1：邊界處理不當 

# ❌ 錯誤：沒有處理插入到末尾的情況
def searchInsert(self, nums: List[int], target: int) -> int:
    for i in range(len(nums)):
        if nums[i] >= target:
            return i
    # 忘記返回 len(nums)！

# ✅ 正確：完整處理所有情況
def searchInsert(self, nums: List[int], target: int) -> int:
    for i in range(len(nums)):
        if nums[i] >= target:
            return i
    return len(nums)  # 插入到末尾

錯誤 2：整數溢出 

# ❌ 可能溢出（雖然 Python 不會，但其他語言會）
mid = (left + right) // 2

# ✅ 防止溢出的寫法
mid = left + (right - left) // 2

錯誤 3：死循環 

# ❌ 錯誤：可能死循環
while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] < target:
        left = mid  # 應該是 mid + 1
    else:
        right = mid  # 應該是 mid - 1

變體問題

1. 如果數組有重複元素？ 

def searchInsertWithDuplicates(nums: List[int], target: int) -> int:
    """返回第一個 >= target 的位置"""
    left, right = 0, len(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left

2. 如果要返回最後一個插入位置？ 

def searchInsertLast(nums: List[int], target: int) -> int:
    """如果有相同元素，插入到最後"""
    left, right = 0, len(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:  # 注意這裡是 <=
            left = mid + 1
        else:
            right = mid
    
    return left

3. 如果要返回範圍？ 

def searchRange(nums: List[int], target: int) -> List[int]:
    """返回 target 可以插入的範圍 [first, last]"""
    def findFirst():
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left
    
    def findLast():
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left
    
    return [findFirst(), findLast()]

進階應用

1. 在旋轉數組中搜索插入位置 

def searchInsertRotated(nums: List[int], target: int) -> int:
    """在旋轉排序數組中找插入位置"""
    # 先找到旋轉點
    def findPivot():
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        return left
    
    pivot = findPivot()
    
    # 決定在哪一半搜索
    if pivot == 0 or target < nums[0]:
        return binarySearch(nums, pivot, len(nums) - 1, target)
    else:
        return binarySearch(nums, 0, pivot - 1, target)

2. 浮點數版本 

def searchInsertFloat(nums: List[float], target: float, epsilon: float = 1e-9) -> int:
    """處理浮點數的插入位置"""
    left, right = 0, len(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target - epsilon:
            left = mid + 1
        else:
            right = mid
    
    return left

效能優化

1. 提前終止 

def searchInsertOptimized(nums: List[int], target: int) -> int:
    # 邊界情況提前處理
    if not nums or target <= nums[0]:
        return 0
    if target > nums[-1]:
        return len(nums)
    
    # 正常二分查找
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return left

2. 緩存友好的實現 

def searchInsertCacheFriendly(nums: List[int], target: int) -> int:
    """減少緩存未命中的實現"""
    n = len(nums)
    if n == 0:
        return 0
    
    # 指數搜索找到大概範圍
    bound = 1
    while bound < n and nums[bound] < target:
        bound *= 2
    
    # 在找到的範圍內二分查找
    left = bound // 2
    right = min(bound, n - 1)
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return left

測試案例 

def test_searchInsert():
    test_cases = [
        # (nums, target, expected)
        ([1,3,5,6], 5, 2),
        ([1,3,5,6], 2, 1),
        ([1,3,5,6], 7, 4),
        ([1,3,5,6], 0, 0),
        ([1], 0, 0),
        ([1], 1, 0),
        ([1], 2, 1),
        ([1,3], 2, 1),
        ([1,3,5,7,9], 6, 3),
        ([], 1, 0),  # 空數組
    ]
    
    solution = Solution()
    for nums, target, expected in test_cases:
        result = solution.searchInsert(nums, target)
        assert result == expected, f"Failed: {nums}, {target}"
        print(f"✅ 通過：在 {nums} 中搜索 {target} → 位置 {result}")

相關題目

  1. LeetCode 34: Find First and Last Position of Element in Sorted Array
  2. LeetCode 74: Search a 2D Matrix
  3. LeetCode 153: Find Minimum in Rotated Sorted Array
  4. LeetCode 162: Find Peak Element
  5. LeetCode 278: First Bad Version

時間複雜度比較圖 

數組大小 vs 操作次數：

n = 1,000,000

線性搜索 O(n)：    1,000,000 次
二分查找 O(log n)：      20 次

效率提升：50,000 倍！

總結

這道題展示了二分查找的核心思想：

  1. 理解插入位置：第一個 ≥ target 的位置
  2. 邊界處理是關鍵：特別是數組開頭和結尾
  3. 選擇合適的模板：標準二分或左邊界查找
  4. 記住 left 的含義：循環結束時 left 就是答案

核心要點：

  • 當找不到時，left 指向第一個大於 target 的位置
  • 這正好是插入位置！

面試建議

  1. 先寫出能工作的版本：標準二分查找模板
  2. 處理邊界情況：空數組、頭尾插入
  3. 解釋為什麼返回 left：展示理解深度
  4. 提及時間複雜度：O(log n) 的重要性
  5. 可以提到 bisect：展示 Python 知識
更新於 2024-12-25 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmArrayBinary-Search
返回 | 主頁
0%