35. Search Insert Position

1. 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.

2. Example

Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:
Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:
Input: nums = [1], target = 0
Output: 0

3. Constraints

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

4. Solutions

My Accepted Solution

n = nums.size()
Time complexity : O(logn)
Space complexity : O(1)

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if (target < *nums.begin() || target > *nums.rbegin()) {
            return target < *nums.begin() ? 0 : nums.size();
        }

        int index;
        for (long left = 0, right = nums.size() - 1; left <= right; ) {
            long middle = (left + right) / 2;
            if (nums[middle] < target) {
                left = middle + 1;
            } else {
                index = middle;

                right = middle - 1;
            }
        }

        return index;
    }
};