Python——LeetCode刷题——【35. 搜索插入位置】

题目描述：

解题思路：

题目要求使用时间复杂度为O（log n）的算法，加上题目描述的内容。我们不难想到要用二分查找的思路。
（1）当要查找的值存在时，我们直接使用二分查找的思路去找，然后返回其下标。
（2）个人认为这个问题的难点在于：当要查找的值不存在的时候，将返回要顺序插入这个值的索引位置。
这个我们可以找规律来确定，我们要顺序插入哪个位置！！！


找了一波规律后，我们发现：如果target在数组中找不到的话，他要顺序插入的位置其实就是start的值！！！

代码和注释：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 可以找到的话，返回其下标
        start = 0
        end = len(nums)-1
        while(start <= end):
            mid = (start + end) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                end = mid - 1
            elif nums[mid] < target:
                start = mid + 1
        
        # 找不到的话，返回start值，因为start值就是要顺序插入的位置
        # 这个可以找规律发现
        return start

结果：