LeetCode 筆記 - 35. Search Insert Position

Posted on 標籤
針對已排序數列，尋找目標值的索引或其應插入的位置。本文展示二元搜尋（Binary Search）的變體應用，透過不斷折半範圍，能以對數級時間複雜度快速鎖定定位。這是一篇掌握排序數列搜尋與邊界處理技巧的基礎筆記。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 35. Search Insert Position

給一個 Sorting 過的數列與 target
找出 target 的 index，如果不存在就找出 target 可以插入的 index

解題思維

就實作 Binary Search 就可以解決了

完成✅

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        length = len(nums)
        
        start = 0
        end = length - 1
        
        while start <= end:
            mid = int((start + end) / 2)
            
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
            
        return start
1
2
3
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

也許你也會想看看