Name: Search Insert Position
Difficulty: Easy
Description: Return the index of target, or where target should be in a sorted array
Example:
Input: nums = [1,3,5,6], target = 5 Output: 2 Input: nums = [1,3,5,6], target = 2 Output: 1 Input: nums = [1,3,5,6], target = 7 Output: 4
The solution was quite simple, but I complicated it by initially using a binary search, and then adding conditions to return quickly in certain obvious cases. Based on the data which drove the tests, this gave the best performance:
int searchInsert(vector<int>& nums, int target) {
for(auto i = nums.begin(); i < nums.end(); ++i) {
auto x = *i;
if (x >= target) return static_cast<int>(i - nums.begin());
}
return static_cast<int>(nums.size());
}