[LeetCode Road] Search Insert Position - Solution/C++

35. Search Insert Position

Question:

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.

Example:

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

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

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

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

Input: nums = [1], target = 0
Output: 0

Constraints:

1 <= nums.length <= 10^4

-10^4 <= nums[i] <= 10^4

nums contains distinct values sorted in ascending order.

-10^4 <= target <= 10^4

Source code

Version 1

Idea:
It is an intuitive method, use a loop to match each elements.

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

Version 2

Idea:
The solution is refered to Huahua's Tech Road.
It is an efficient approach to process large size of vector. m = l + (r - 1) / 2 is a key to divide into two parts. Then, get one of parts that consists target (Reduce computing time), repeats it until we find the accurate position.

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