力扣题库第35题-搜索插入位置

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

请必须使用时间复杂度为 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 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

题目要求我们使用时间复杂度为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 <= right:
            middle = (left + right) // 2   # 中间索引
            if nums[middle] == target:
                return middle
            if nums[middle] > target:
                right = middle - 1
            if nums[middle] < target:
                left = middle + 1
        if left > right:
            return left

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