```
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int s = 0, e = nums.size()-1,m;
// Invariant for binary search
while(e>=s){
// Midpoint formula to avoid overflow
m = s + (e-s)/2;
// while searching, return the index if target is found OR
// check if the present element is greater than target and prev element
// is smaller(or equal to, but since no duplicates, we can avoid that confusion)
// than target(also ensure that it is not at the beginning of range
// by checking m == s)
if(nums[m] == target || (nums[m] > target && (m == s || nums[m-1] < target))) return m;
//Update the range on binary search
else if(nums[m] < target) s = m + 1;
else e = m - 1;
}
// If target is greater than largest element in array, then insert it beyond the last position
return nums.size();
}
};
```