leetcode35.搜素插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

解答：
方法一：
时间复杂度：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