```
class Solution
{
public:
int searchInsert(vector<int>& nums, int target)
{
int lo = 0, hi = nums.size(), mid;
// find index whose value first is greater than target
while(lo < hi)
{
mid = (lo + hi) / 2;
if (nums[mid] > target) hi = mid;
else lo = mid + 1;
}
// find the target?
if (lo > 0 && nums[lo - 1] == target) --lo;
return lo;
}
};
```