LeetCode: Search Insert Position

Posted on January 16, 2018July 26, 2020 by braindenny

Search Insert Position

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution binary search

## https://code.dennyzhang.com/search-insert-position
## Basic Ideas: binary search
##
## Complexity: Time O(log(n)), Space O(1)
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums: return 0
        if nums[-1] < target:
            return len(nums)
        left, right = 0, len(nums)-1
        # May not exists
        while left<=right:
            mid = int((right-left)/2+left)
            if target == nums[mid]:
                return mid

            if target > nums[mid]:
                # drop the left half
                left = mid + 1
            else:
                right = mid - 1
        # right, left
        return left

// https://code.dennyzhang.com/search-insert-position
// Basic Ideas: binary search
//
// Complexity: Time O(n*log(n)), Space O(1)
func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left<=right {
        mid := (right-left)/2+left
        if nums[mid] == target {
            return mid
        }
        if nums[mid] < target {
            left = mid+1
        } else {
            right = mid-1
        }
    }
    return left
}

Post Views: 5