Coding Exercise - Search Insert Position 编程练习题 - 寻找插入位置

justyy (81)in #programming • 6 years ago (edited)

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

O(n) naive solution

Try from the begining of the array and see if it is bigger or equal than the current element, thanks to the fact that the vector is already sorted. One pass if we don't find the target i.e. the number to insert is bigger than all the numbers, we need to insert the number at the end of the vector.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for (auto i = 0; i < nums.size(); ++ i) {
            if (nums[i] >= target) {
                return i;
            }
        }
    }
};

O(logn) solution - binary search

We know the array is sorted, so we can reduce the search to O(logN) via binary search. If not found, i>=j then we need to compare target with the nums[i], return i + 1 if the target is bigger (insert after) or i otherwise (insert before).

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