今天是紀錄LeetCode解題的第三十五天

第三十五題題目：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，如果找到target在nums中的索引則回傳該索引，否則回傳target在nums中的插入位置的索引

時間複雜度須為O(log n)

解題思路

這題也是用二分搜尋的方式，設left,right = 0,len(nums) - 1，算出中點mid，判斷target落在mid的左邊則縮小右邊界(right = mid - 1)，落在右邊則縮小左邊界(left = mid + 1)，最後回傳left就是target在nums中的索引，如果target不存在於nums中，left則會是插入位置的索引

程式碼

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left,right = 0,len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left
        

執行過程

初始狀態

• nums = [1,3,5,6]
• target = 2
• left = 0
• right = len(nums) - 1 = 3

第一次執行

• mid = (left + right) // 2 = (0 + 3) // 2 = 1
• nums[mid] < target → 3 < 2 → False
• right = mid - 1 = 0

第二次執行

• mid = (left + right) // 2 = (0 + 0) // 2 = 0
• nums[mid] < target → 1 < 2 → True
• left = mid + 1 = 1
• left > right → 1 > 0 → 結束迴圈，回傳left = 1

有前兩天二分搜尋的Medium題目，今天這題寫起來應該相當簡單