题目描述

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

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

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 

解析

题目要求我们使用时间复杂度为O(log₂n)的算法，那就不能简单粗暴的进行遍历了，根据题目的数组是有序的，我们能够很容易想到使用二分法查找数据，如果我们找到middle偏移的元素等于target，那么我们就可以直接返回middle，如果没有找到元素，只要在退出循环的时候直接返回left的值就可以了。因为非常简单，这里不做过多赘述！

直接看代码：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 显然，需要使用二分查找
        left= 0
        right= len(nums) -1
        while left  target:
                right = middle - 1
            if nums[middle]  right:
            return left

总结

一个小知识点：如果数组是有序的，那么在查找的时候可以使用二分查找法，时间复杂度为O(log₂n)!