Leetcode如何搜索插入位置

Leetcode如何搜索插入位置

在算法和數據結構的學習過程中，二分查找（Binary Search）是一個非常重要的基礎算法。它不僅高效，而且應用廣泛。Leetcode上的“搜索插入位置”問題（Search Insert Position）就是一個典型的二分查找應用場景。本文將詳細講解如何使用二分查找來解決這個問題，并分析其時間復雜度和空間復雜度。

問題描述

題目鏈接：Leetcode 35. 搜索插入位置

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

你可以假設數組中無重復元素。

示例 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

示例 4:

輸入: nums = [1,3,5,6], target = 0
輸出: 0

解題思路

暴力解法

最直觀的解法是遍歷整個數組，找到第一個大于或等于目標值的元素，返回其索引。如果遍歷結束后仍未找到，則返回數組的長度。

def searchInsert(nums, target):
    for i in range(len(nums)):
        if nums[i] >= target:
            return i
    return len(nums)

時間復雜度： O(n)，其中 n 是數組的長度。最壞情況下需要遍歷整個數組。

空間復雜度： O(1)，只使用了常數級別的額外空間。

雖然暴力解法簡單易懂，但在最壞情況下時間復雜度較高，無法充分利用數組已排序的特性。

二分查找

由于數組是有序的，我們可以使用二分查找來優化時間復雜度。二分查找的基本思想是通過不斷縮小搜索范圍來快速定位目標值。

步驟如下：

1. 初始化左右指針 left 和 right，分別指向數組的起始和末尾。
2. 計算中間位置 mid，并比較 nums[mid] 與 target 的大小。
   • 如果 nums[mid] == target，則直接返回 mid。
   • 如果 nums[mid] < target，則目標值在右半部分，更新 left = mid + 1。
   • 如果 nums[mid] > target，則目標值在左半部分，更新 right = mid - 1。
3. 重復步驟2，直到 left 超過 right。
4. 如果未找到目標值，則返回 left，即目標值應該插入的位置。

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left

時間復雜度： O(log n)，其中 n 是數組的長度。每次迭代都將搜索范圍縮小一半。

空間復雜度： O(1)，只使用了常數級別的額外空間。

邊界條件分析

在使用二分查找時，需要注意一些邊界條件：

1. 空數組： 如果數組為空，直接返回0。
2. 目標值小于數組最小值： 如果目標值小于數組的第一個元素，返回0。
3. 目標值大于數組最大值： 如果目標值大于數組的最后一個元素，返回數組的長度。

這些邊界條件在代碼中已經通過 left 和 right 的更新邏輯自動處理，因此無需額外判斷。

代碼實現

以下是完整的Python代碼實現：

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left

測試用例

為了驗證代碼的正確性，我們可以使用題目中的示例進行測試：

nums = [1, 3, 5, 6]
targets = [5, 2, 7, 0]
for target in targets:
    print(searchInsert(nums, target))

輸出結果：

2
1
4
0

與題目中的示例結果一致，說明代碼正確。

總結

通過二分查找，我們可以在 O(log n) 的時間復雜度內解決“搜索插入位置”問題。相比于暴力解法的 O(n) 時間復雜度，二分查找在效率上有顯著提升。在實際應用中，二分查找是處理有序數組問題的首選方法。

掌握二分查找的關鍵在于理解其核心思想：通過不斷縮小搜索范圍來快速定位目標值。同時，需要注意邊界條件的處理，以確保代碼的魯棒性。

希望本文的講解能夠幫助你更好地理解和掌握二分查找算法，并在Leetcode等編程挑戰中靈活運用。