0035. 搜索插入位置

0035. 搜索插入位置 #

  • 标签:数组、二分查找
  • 难度:简单

题目大意 #

描述:给定一个排好序的数组 nums,以及一个目标值 target

要求:在数组中找到目标值,并返回下标。如果找不到,则返回目标值按顺序插入数组的位置。

说明

  • $1 \le nums.length \le 10^4$。
  • $-10^4 \le nums[i] \le 10^4$。
  • $nums$ 为无重复元素的升序排列数组。
  • $-10^4 \le target \le 10^4$。

示例

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

解题思路 #

思路 1:二分查找 #

设定左右节点为数组两端,即 left = 0right = len(nums) - 1,代表待查找区间为 [left, right](左闭右闭)。

取两个节点中心位置 mid,先比较中心位置值 nums[mid] 与目标值 target 的大小。

  • 如果中心位置值 nums[mid] 与目标值 target 相等,则当前中心位置为待插入数组的位置。
  • 如果中心位置值 nums[mid] 小于目标值 target,则将左节点设置为 mid + 1,然后继续在右区间 [mid + 1, right] 搜索。
  • 如果中心位置值 nums[mid] 大于目标值 target,则将右节点设置为 mid - 1,然后继续在左区间 [left, mid - 1] 搜索。

直到查找到目标值返回待插入数组的位置,或者等到 left > right 时停止查找,此时 left 所在位置就是待插入数组的位置。

思路 1:二分查找代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        size = len(nums)
        left, right = 0, size - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left

思路 1:复杂度分析 #

  • 时间复杂度:$O(\log n)$。二分查找算法的时间复杂度为 $O(\log n)$。
  • 空间复杂度:$O(1)$。只用到了常数空间存放若干变量。
本站总访问量  次  |  您是本站第  位访问者