1 minute read

35. Search Insert Position

Difficulty: Easy

Related Topics: Binary Search, Array

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5 Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2 Output: 1

Example 3:

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

First Attempt:

Code:

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

Feedbacks:

Even I got it right at first attempt using binary search slightly, it seems theres a lot to be improved.

Second Attempt:

Code:

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

Feedbacks:

The biggest difference between other binary search problem is when “mid” is larget than target number, right becomes mid, not mid -1, and return left not mid. Should do more practices in binary search.

You may also enjoy