LeetCode: Search Insert Position

\(\)

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

After finishing binray search, the lo pivot is the index with element larger or equal with target.

Time complexity: \(O(logN)\).

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!

Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *