start stores the in-valid position, end stores the biggest valid position.

```
(start, end]
```

Code:

```
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.size()==0) return 0;
int start=-1, end=nums.size();
while(end-start>1){
int mid=(start+end)/2;
if(target <= nums[mid]) end=mid;
else start=mid;
}
return end;
}
};
```