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

1class Solution:
2    def searchInsert(self, nums: List[int], target: int) -> int:
3        if target > nums[-1]:
4            return len(nums)
5        for i in range(len(nums)):
6            if target <= nums[i]:
7                return i
8        return len(nums)

Approach 2: binary search

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.

1class Solution:
2    def searchInsert(self, nums: List[int], target: int) -> int:
3        low = 0
4        high = len(nums)-1
5        while low <= high:
6            mid = (high + low) // 2
7            if nums[mid] == target:
8                return mid
9            elif nums[mid] < target:
10                low = mid + 1
11            else:
12                high = mid - 1
13        return low