Search Insert Position

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.

You must write an algorithm with O(log n) runtime complexity.

For example:

1. nums = [1,3,5,6], target = 5 should return 2.
2. nums = [1,3,5,6], target = 2 should return 1.
3. nums = [1,3,5,6], target = 7 should return 4.

Write a function to solve this problem efficiently.

## Search Insert Position

This problem requires us to find the index of a target value in a sorted array. If the target is not found, we need to return the index where it would be inserted to maintain the sorted order. The key constraint is to achieve this with O(log n) runtime complexity, which strongly suggests using binary search.

### 1. Naive Solution (Linear Search)

A simple, but inefficient, approach would be to iterate through the array and check if the target is found. If not, we determine the insertion point by finding the first element greater than the target.

```python
def search_insert_naive(nums, target):
    for i in range(len(nums)):
        if nums[i] >= target:
            return i
    return len(nums)

This solution has a time complexity of O(n) because, in the worst case, we might need to iterate through the entire array.

2. Optimal Solution (Binary Search)

To achieve O(log n) runtime, we can use binary search. Binary search repeatedly divides the search interval in half. If the middle element is the target, we return its index. If the target is less than the middle element, we search the left half; otherwise, we search the right half. If the target is not found, the search eventually narrows down to an interval of size zero, at which point we can determine the insertion point.

def search_insert(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return left

3. Big(O) Runtime Analysis

The binary search algorithm divides the search space in half at each step. Therefore, the number of steps required to find the target (or the insertion point) is logarithmic with respect to the size of the input array n. Specifically, it takes at most log₂(n) steps. Thus, the time complexity is O(log n).

4. Big(O) Space Usage Analysis

The algorithm uses a constant amount of extra space, regardless of the input size. We only use a few variables (left, right, mid) to keep track of the search boundaries. Therefore, the space complexity is O(1).

5. Edge Cases and Handling

• Empty Array: If the input array is empty, the algorithm should return 0, as the target would be inserted at the beginning.
• Target Smaller than First Element: If the target is smaller than the first element in the array, the algorithm should return 0, indicating that the target should be inserted at the beginning.
• Target Larger than Last Element: If the target is larger than the last element in the array, the algorithm should return the length of the array, indicating that the target should be inserted at the end.
• Duplicate Values: The problem states that the array contains distinct values, so we don't need to handle duplicate values.
• Large Input Size: The algorithm should perform efficiently even with a large input size due to its logarithmic time complexity.

Here's the code with edge case handling included:

def search_insert(nums, target):
    if not nums:
        return 0
        
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return left