# A Binary-search based C++ solution with explanation

• First of all, this problem is equivalent to finding the index of first element in `nums` which does not compare less than the `target`, or to say, it is a lower bound problem.

Suppose the index of `nums` is 0, 1, 2, ... , n

The valid lower bound index is actually 0, 1, 2, ... , n, n+1 (Note the `n+1` is inclusive). so we do initialization as below in the solution.

``````int lower_bound(vector<int>& nums, int target) {
// NOTE: range of index is [0, nums.size()]
// the begin is the index of the possible lower bound
size_t begin = 0, end = nums.size(), mid;
while( begin < end ) {
mid = (begin + end) / 2;
if(nums[mid] >= target ) end = mid;
else begin = mid+1;
}
return begin;
}
``````

Every iteration, if `nums[mid] >= target`, move the `end` to `mid`.

Since `begin < end` and we calculate `mid` by `(begin + end) / 2`, the `mid` will at least 1 smaller then `end`.

If not, `nums[mid]` is less then `target`, so move `begin` 1 step after `mid`.

• ``````class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.empty())
return 0;

vector<int>::iterator iter = find(nums.begin(), nums.end(), target);

if(iter != nums.end())
return iter - nums.begin();
else{
for(iter = nums.begin(); iter != nums.end(); iter++){
if(*iter > target)
return iter - nums.begin();
}
}
return nums.size();
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.