LeetCode 35 Search Insert Position

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.

Examples

[1, 3, 5, 6], 5 → 2
[1, 3, 5, 6], 2 → 1
[1, 3, 5, 6], 7 → 4
[1, 3, 5, 6], 0 → 0

Difficulty
Medium

Analysis

This is a variation of Binary search.

Two situations

1. Binary search the target value in the array, if we find it when low <= high, return mid.
2. If we failed in the above, this means low > high, we return low.

Explanation

When we failed, that means we need to find the first element whose value is greater than the target value, its index is position where we will insert the new value. e.g. for [1, 3, 5, 6], we search for 2, we know that 3 is the first element with value greater than 2. Its index is the position we will insert 2.

Solutions

1. Cpp solution 6ms

class Solution {
public:
    int searchInsert(vector<int>& A, int target) {
        int n = A.size();
        int low = 0, high = n-1;
        while(low <= high){
            int mid = low + (high-low)/2;
            if(target == A[mid]) 
                return mid;
            else if(target < A[mid])
                high = mid-1;
            else
                low = mid+1;
        }
        return low;
    }
};

1. Go solution 9ms

Note: Go standard sort package provides a func SearchInts(a []int, x int) int to do binary search to a sorted slice. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.

func searchInsert(nums []int, target int) int {
    n := len(nums)
    low, high := 0, n-1
    for low <= high {
        mid := low + (high-low)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] > target {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return low
}

Reference