35. Search Insert Position

Category: Binary Search & Array

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.

Example 1:

Input: [1,3,5,6], 5 Output: 2

Example 2:

Input: [1,3,5,6], 2 Output: 1

Example 3:

Input: [1,3,5,6], 7 Output: 4

Example 4:

Input: [1,3,5,6], 0 Output: 0

Solution


Approach 1: traverse
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target > nums[-1]:
            return len(nums)
        for i in range(len(nums)):
            if target <= nums[i]:
                return i
        return len(nums)

The time complexity of the above solution is O(n) and that's not so bad, but we can achieve better performance O(log n) if we will use binary search.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums)-1
        while low <= high:
            mid = (high + low) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return low

评论

暂无评论