For the last week or so I haven't done much LC. Most of my time has been dedicated to setting up staging environment for this site and getting a CI/CD pipeline built. Also, planning out the admin panel for this site to make posting more seamless. More to come on this! In the meantime figured I'd post a quick solution.
Approach
The objective is to find the index of the target and if it's not in the array, return the index it would be at. It also mentions the algorithm must be in O(log n) time.
To me this sounds like a classic binary search problem. My mind always goes to the recursive approach when implementing binary search but here I used the iterative approach. As a side note, LeetCode rarely has the function signatures to support the recursive approach.
Rather than explain the entirety of this I'll simply refer to GeeksForGeeks which does a great job explaining the two approaches to binary search.
Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Code
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
} else {
if(target > nums[mid]){
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return left;
}
};