Search Insert Position

Given a sorted array of distinct integers and a target value, find the index where the target should be inserted to maintain the sorted order. If the target is already present in the array, return its index. This is a common operation in data structures and algorithms, essential for maintaining sorted collections efficiently.

Problem Description

You will be given a sorted array of distinct integers and a target integer. Your task is to implement a function that returns the index where the target value should be inserted into the nums array so that the array remains sorted. If the target already exists in the nums array, you should return the index of that element.

Key Requirements:

• The input nums array is guaranteed to be sorted in ascending order.
• The input nums array contains distinct integers (no duplicates).
• The function should return an integer representing the correct insertion index.

Expected Behavior:

• If the target is found in the array, return its index.
• If the target is not found, return the index where it would be inserted.
• The index returned should be valid, meaning it's within the bounds of the array or one position past the end if the target is larger than all elements.

Edge Cases to Consider:

• An empty nums array.
• The target being smaller than all elements in nums.
• The target being larger than all elements in nums.
• The target being present in nums.

Examples

Example 1:

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: The target '5' is found at index 2.

Example 2:

Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Explanation: The target '2' is not found. If it were inserted, it would be at index 1 to maintain the sorted order: [1, 2, 3, 5, 6].

Example 3:

Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Explanation: The target '7' is not found. If it were inserted, it would be at index 4 (one position past the end) to maintain the sorted order: [1, 3, 5, 6, 7].

Example 4:

Input: nums = [1, 3, 5, 6], target = 0
Output: 0
Explanation: The target '0' is not found. If it were inserted, it would be at index 0 to maintain the sorted order: [0, 1, 3, 5, 6].

Example 5:

Input: nums = [], target = 0
Output: 0
Explanation: The array is empty. The target '0' would be inserted at index 0.

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

Notes

Consider the efficiency of your solution. A brute-force linear scan will work, but a more optimal approach leveraging the sorted nature of the array would be preferable. Think about how you can quickly narrow down the search space.