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