python leetcode35:搜索插入位置

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

法一：比較法

class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] == target: #相等
return i
elif i < len(nums)-1 and target > nums[i] and target < nums[i+1] : #target處於中間位置
return i+1
elif i == 0 and target < nums[i]: #開頭
return i
return len(nums) #不存在於數組

法二：二分查找

直接套用二分法即可，即不斷用二分法逼近查找第一個大於等於 \textit{target}target 的下標 。

class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)-1
while l <= r:
mid = (l+r)//2
if target == nums[mid]:
return mid
elif target < nums[mid]:
r = mid - 1
else:
l = mid +1
return l
nums = [1, 3, 5, 6]
target = 7
S = Solution()
result = S.searchInsert(nums,target)
print(result)