leetcode35.搜素插入位置

题目:
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。
leetcode35.搜素插入位置_第1张图片

解答:
方法一:
时间复杂度:O(n)
空间复杂度:O(1)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n=len(nums)
        for i in range(n):
            if target<=nums[i]:
                return i
        return n

方法二:二分法
(1)左闭右闭

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        #二分法,左闭右闭
        n=len(nums)
        left,right=0,n-1
        while left<=right:
            mid=left+(right-left)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right=mid-1
            else:
                left=mid+1
        return left

(2)左闭右开

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        #二分法,左闭右开
        n=len(nums)
        left,right=0,n
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right=mid
            else:
                left=mid+1
        return left

你可能感兴趣的