The problem is taken from 35. Search Insert Position.

Approach

The solution is very straight forward. We need to do binary search on the given array and try to find the target value. But the catch here is, if the target value is not found in the array then we have to return the perfect possible position for it.

Let's see the code first-

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size(); // size  of array
        int low = 0, high = n-1;

        while(low<=high) {
            int mid = low + (high - low)/2; // we escaped integer overflow(I'll talk about it)
            if(nums[mid] == target) // we found
                return mid;
            else if(nums[mid] > target) // search in left half
                high = mid-1;
            else // search in right half
                low = mid+1;

        }

        return low;
    }
};

Explanation 1.0

Let's take a example - nums = [1,2,4,5] and target = 3

Step 1-

[ 1,    2,       4,     5]

 i                    j

mid = 1

nums[mid] < target => search in right half

Step 2-

          [ ,    ,       4,     5] 
                         i      j

mid = 2

nums[mid] > target => search in left half

Step 3-

          [ ,    ,       4,     ] 
                        i         
                        j

mid = 2

nums[mid] > target => nothing more to search

So if the target value exists in the array, the value of low will always be <=(less than or equal to) high. But if the target value is not present in the array, the loop will halt when high is < low. (See code now) That means just before halting loop condition low and high were same and that's the position our target value can possibly reside in.

Explanation 1.1

 int mid = low + (high - low)/2;

An integer variable can hold a maximum value of 2^32 - 1. So if sum of low and high surpasses the maximum value of integer then this mid=(low+high) causes integer overflow and mid get assigned with a negative value which will give us a index error in future.

So to avoid this scenario we used above mentioned code.

Complexity

Time - O(log(n)), due to use of binary search method.

Space - O(1), no extra space is used.