Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

1
2
3
4
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

思路

本题我就利用O(n)的时间复杂度，鉴于题目难度，时间上还是可以接受的。
如果需要优化，可以用二分查找法，在利用二分查找法的时候注意边界条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        ans = 0
        length = len(nums)
        
        for i in range(length):
            if target > nums[i]:
                ans = i + 1
            elif target == nums[i]:
                ans = i
                break
            else:
                break
        return ans