Return the index where a target should be inserted into a sorted array.

Interview question: Search Insert Position

Given a sorted array of distinct integers `nums` and a target value `target`, return the index if the target is found. If not, return the index where it would be inserted to keep the array sorted.

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

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

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

- If `target` exists in the sorted array, return its index.
- If it does not exist, return the position where it could be inserted while keeping the array sorted.
- That insertion position is the first index whose value is greater than or equal to `target`.

Understand the Return Value

- A simple solution checks values from left to right.
- Return the first index where `nums[i] >= target`.
- This is easy but O(n), while the problem asks for O(log n).

Linear Scan Idea

- Because `nums` is sorted, binary search can discard half of the remaining positions each step.
- Keep a search window `[left, right)` where `right` is exclusive.
- The answer will be the smallest index where the value is at least `target`.

Use Binary Search

- If `nums[mid] < target`, the insertion point must be to the right of `mid`.
- Otherwise, `mid` might be the answer, so keep it by moving `right` to `mid`.
- When the window is empty, `left` is the insertion index.

Move the Bounds

- The same binary search handles found and not-found cases.
- Time complexity is O(log n) because the window halves each iteration.
- Space complexity is O(1).