Search Insert Position

Description

• Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Constraints

• 1 <= n <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

Test Cases

• 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

Code

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

int searchInsert(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] >= target) {
            return i;
        }
    }
    return nums.size();
}