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)

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.

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