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.

Here are few 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

Approach 1: Use modified binary search to get the required index

class Solution {
public:
    // recursive modified binary search
    int insertPos(vector<int> &nums, int low, int high, int target){
        //base case with 1 element
        if(low == high){
            if(nums[low] < target){
                return low + 1;
            }else{
                return low;
            }
        }
        //base case with 2 elements
        if(low == high - 1){
            if(nums[high] < target){
                return high + 1;
            }else if(target <= nums[low]){
                return low;
            }else{
                return high;
            }
        }
        //recursive call based on the index 
        int mid = low + ((high - low) >> 1);
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] < target && nums[mid + 1] > target){
            return mid + 1;
        }else if(nums[mid] > target){
            return insertPos(nums, low, mid - 1, target);
        }else{
            return insertPos(nums, mid + 1, high, target);
        }
    }
    
    int searchInsert(vector<int>& nums, int target) {
        return insertPos(nums, 0, nums.size()-1, target);
    }
};

Approach 2: Use lower_index() method supported by STL

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        vector<int>::iterator it = lower_bound(nums.begin(), nums.end(), target);
        return (it - nums.begin());
    }
};

Here is the link to the ideone solution : http://ideone.com/TbFRxX