Challenge Description

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], 7
Output: 4

Naive Solution

The insert position is the index which element’s value is greater or equal with target.

So we scan linearly the array will find the answer.

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

Approach with Binary Search

When the target element is in array, binary search will found the position in time complexity of $O(logN)$.

For an increasing array, if the target is not in array, the ended lo pivot will be the index of element with value larger or equal with target.

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

Preparing for an interview? Check out this!