题目描述

[EN | CN]

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

你可以假设数组中无重复元素。

示例 1:

1
2
输入: [1, 3, 5, 6], 5
输出: 2

示例 2:

1
2
输入: [1, 3, 5, 6], 2
输出: 1

示例 3:

1
2
输入: [1, 3, 5, 6], 7
输出: 4

示例 4:

1
2
输入: [1, 3, 5, 6], 0
输出: 0

解法 1:二分查找

直接用二分查找即可完成。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(\log n)$,二分查找复杂度;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        length = len(nums)
        if length == 0 or nums[0] > target:
            return 0
        elif nums[length - 1] < target:
            return length

        i, j = 0, length - 1
        while i < j:
            m = (i + j) // 2
            if nums[m] == target:
                return m
            if nums[m] > target:
                j = m - 1
            else:
                i = m + 1
        if nums[i] < target and nums[i + 1] > target:
            return i + 1
        else:
            return i
  • 执行用时:32 ms,在所有 Python3 提交中击败了 97.20% 的用户。
  • 内存消耗:14.1 MB,在所有 Python3 提交中击败了 7.14% 的用户。